Быстрое возведение в степень - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:18:38Z

rollbackEdits.php mass rollback

171.25.193.80 в 05:31, 1 сентября 2022

2022-09-01T05:31:14Z

216.252.79.20: /* Функция быстрого возведения в степень */

2016-09-11T06:08:40Z

‎Функция быстрого возведения в степень

Shersh в 12:05, 7 мая 2014

2014-05-07T12:05:19Z

Bochkarev в 01:46, 13 октября 2010

2010-10-13T01:46:04Z

Bochkarev в 22:19, 11 октября 2010

2010-10-11T22:19:43Z

Bochkarev в 18:03, 8 октября 2010

2010-10-08T18:03:42Z

192.168.0.2: Новая страница: «'''Алгоритм быстрого возведения в степень''' — алгоритм, предназначенный для возведения чи…»

2010-10-08T17:43:30Z

Новая страница: «'''Алгоритм быстрого возведения в степень''' — алгоритм, предназначенный для возведения чи…»

Новая страница

'''Алгоритм быстрого возведения в степень''' — алгоритм, предназначенный для возведения числа ''x'' в натуральную степень ''n'' за меньшее число умножений, чем это требуется в определении.

@@ Строка 1: / Строка 1: @@
-{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
+'''Алгоритм быстрого возведения в степень''' — алгоритм, предназначенный для возведения числа ''x'' в натуральную степень ''n'' за меньшее число умножений, чем это требуется в определении.
-Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
+Пусть <tex>m=(m_{k}m_{k-1}...m_{1}m_{0})_2</tex> — двоичное представление степени ''n''. Тогда <tex>n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+...+m_{1} \cdot 2+m_{0}</tex>, где <tex>m_{k}=1, m_{i} \in \{ 0,1 \}</tex> и <tex>x^{n}=x^{((...((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+...) \cdot 2+m_{1}) \cdot 2 + m_{0}}</tex>. <br>
 == Функция быстрого возведения в степень ==

@@ Строка 1: / Строка 1: @@
-'''Алгоритм быстрого возведения в степень''' — алгоритм, предназначенный для возведения числа ''x'' в натуральную степень ''n'' за меньшее число умножений, чем это требуется в определении.
+{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
-Пусть <tex>m=(m_{k}m_{k-1}...m_{1}m_{0})_2</tex> — двоичное представление степени ''n''. Тогда <tex>n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+...+m_{1} \cdot 2+m_{0}</tex>, где <tex>m_{k}=1, m_{i} \in \{ 0,1 \}</tex> и <tex>x^{n}=x^{((...((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+...) \cdot 2+m_{1}) \cdot 2 + m_{0}}</tex>. <br>
+Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 == Функция быстрого возведения в степень ==

@@ Строка 4: / Строка 4: @@
 == Функция быстрого возведения в степень ==
-Функция int '''Power'''(int value, int pow)
+ '''function''' Power(value, pow: '''int'''): '''int'''
-. int result = 1;
+   '''int''' result = 1
-. while (pow) {
+   '''while''' (pow > 0)
-.     if (pow & 1) result *= value;
+     '''if''' pow '''mod''' 2 == 1
-.     value *= value;
+       result *= value
-.     pow >>= 1;
+     value *= value
-. }
+     pow /= 2;
-. return result;
+   '''return''' result;
 == Ссылки ==
 * [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.8878&rep=rep1&type=pdf BinPow and 2^k-ary pow]
 * [http://cr.yp.to/bib/2003/joye-ladder.pdf Montgomerry Ladder]

← Предыдущая		Версия 12:05, 7 мая 2014
Строка 12:		Строка 12:
	6. }		6. }
	7. return result;		7. return result;
		+
		+	== Ссылки ==
		+	* [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.8878&rep=rep1&type=pdf BinPow and 2^k-ary pow]
		+	* [http://cr.yp.to/bib/2003/joye-ladder.pdf Montgomerry Ladder]

@@ Строка 1: / Строка 1: @@
 '''Алгоритм быстрого возведения в степень''' — алгоритм, предназначенный для возведения числа ''x'' в натуральную степень ''n'' за меньшее число умножений, чем это требуется в определении.
-Пусть <tex>m=(m_{k}m_{k-1}...m_{1}m_{0})_2</tex> — |двоичное представление степени ''n''. Тогда <tex>n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+...+m_{1} \cdot 2+m_{0}</tex>, где <tex>m_{k}=1, m_{i} \in \{ 0,1 \}</tex> и <tex>x^{n}=x^{((...((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+...) \cdot 2+m_{1}) \cdot 2 + m_{0}}</tex>. <br>
+Пусть <tex>m=(m_{k}m_{k-1}...m_{1}m_{0})_2</tex> — двоичное представление степени ''n''. Тогда <tex>n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+...+m_{1} \cdot 2+m_{0}</tex>, где <tex>m_{k}=1, m_{i} \in \{ 0,1 \}</tex> и <tex>x^{n}=x^{((...((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+...) \cdot 2+m_{1}) \cdot 2 + m_{0}}</tex>. <br>
 == Функция быстрого возведения в степень ==

← Предыдущая		Версия 22:19, 11 октября 2010
Строка 2:		Строка 2:

	Пусть <tex>m=(m_{k}m_{k-1}...m_{1}m_{0})_2</tex> — \|двоичное представление степени ''n''. Тогда <tex>n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+...+m_{1} \cdot 2+m_{0}</tex>, где <tex>m_{k}=1, m_{i} \in \{ 0,1 \}</tex> и <tex>x^{n}=x^{((...((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+...) \cdot 2+m_{1}) \cdot 2 + m_{0}}</tex>. <br>		Пусть <tex>m=(m_{k}m_{k-1}...m_{1}m_{0})_2</tex> — \|двоичное представление степени ''n''. Тогда <tex>n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+...+m_{1} \cdot 2+m_{0}</tex>, где <tex>m_{k}=1, m_{i} \in \{ 0,1 \}</tex> и <tex>x^{n}=x^{((...((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+...) \cdot 2+m_{1}) \cdot 2 + m_{0}}</tex>. <br>
		+
		+	== Функция быстрого возведения в степень ==
		+	Функция int '''Power'''(int value, int pow)
		+	1. int result = 1;
		+	2. while (pow) {
		+	3. if (pow & 1) result *= value;
		+	4. value *= value;
		+	5. pow >>= 1;
		+	6. }
		+	7. return result;

← Предыдущая		Версия 18:03, 8 октября 2010
Строка 1:		Строка 1:
	'''Алгоритм быстрого возведения в степень''' — алгоритм, предназначенный для возведения числа ''x'' в натуральную степень ''n'' за меньшее число умножений, чем это требуется в определении.		'''Алгоритм быстрого возведения в степень''' — алгоритм, предназначенный для возведения числа ''x'' в натуральную степень ''n'' за меньшее число умножений, чем это требуется в определении.
		+
		+	Пусть <tex>m=(m_{k}m_{k-1}...m_{1}m_{0})_2</tex> — \|двоичное представление степени ''n''. Тогда <tex>n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+...+m_{1} \cdot 2+m_{0}</tex>, где <tex>m_{k}=1, m_{i} \in \{ 0,1 \}</tex> и <tex>x^{n}=x^{((...((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+...) \cdot 2+m_{1}) \cdot 2 + m_{0}}</tex>. <br>