Кстати, была интересная ветка про возведение в встепень

← →
TStas © (2006-02-28 23:55) [0]

... с миниммальным кол-вом умножений. Я когда модуль больших чисел писал решил для себя эту задачу, эффектиивность - потрясающая. В 1000 степень возводится за 13! умножений. Есть готовый модуль, апритом давно висит, даже с парсером. Не знаю, почему сейчас вспомнил.

← →
wicked © (2006-02-28 23:58) [1]

за 13! умножений.... хм.... мож лучше простым перебором?.... а то факториал - штука быстро-растущая....

← →
iZEN © (2006-03-01 00:13) [2]

TStas © (28.02.06 23:55), неужели додумались использовать логарифмы? ;)

← →
TStas © (2006-03-01 00:30) [3]

Нет. Общая идея совершенно другая. Нужно найти степень двойки, которая меньше показателя степени. Возвести... Я потом ссылку дам. А далее запомнить число во всех нужгных показателях, равных степенях 2. Приммер с 1000. Мин степень 2 - 512. Возводим, пусть число х. х*х=x^2
И. т. д. умножая на себя получаяем в 4, 8, 16, 32, 64, 128, 256, 512. Ни одного лишнего действия, только числа при этом запомнили. 1000-512=488, т. е. останлость возвести y:=x^512 в 488. Опять из ГОТОВЫХ степеней дерем длижайшее к 488, это 256 и делаем еще ОДНО умножение y:=y*x^256, остается степень 488-256=232, поступаем так, пока не дойдет до 0 или 1. То есть , затем у умножаем на х в 128, 232-128=104, затем также ОДНО умножение 104-64=40, 40-32=8. 8-8=0 . Логорифмы - глумление. Задача оптимизировать скорость рассчентов, а не слеписть отмазку. Вот ссылка http://stas258.narod.ru/frame/download/VeryLongMath.zip
Мой 7-значный телефон возводит в 1000 степень, пересчитывает в строку и выводит ее, еще и парсит простое выражение за 170 мс.
ИМХО не плохо

← →
TStas © (2006-03-01 00:43) [4]

>wicked знак ! после числа 13 не означает факториал. Это выражение эмоции, что в 1000 степень за 13 умножнений

← →
jack128 © (2006-03-01 00:53) [5]

TStas © (01.03.06 0:30) [3]
Общая идея совершенно другая. Нужно найти степень двойки, которая меньше показателя степени
не поверишь, подобная функция есть в стандартной поставке дельфи. Называется IntPower, модуль Math. Правда она естественно не для "больших" , а для обычных чисел..

← →
iZEN © (2006-03-01 03:02) [6]

TStas © (01.03.06 00:30) [3], классно.

Ещё можно пакет java.math из поставки Sun J2SE SDK рассмотреть.
Там в исходниках (src.zip) есть класс java.math.BigDecimal, работающий с большими числами, - вся арифметика над строковым представление n-разрядного числа.

← →
pasha_golub © (2006-03-01 06:51) [7]

> iZEN © (01.03.06 03:02) [6]

> Ещё можно пакет java.math из поставки Sun J2SE SDK рассмотреть.

Я бы жутко удивился, не услышав от тебя про Джаву. ;0)

← →
MBo © (2006-03-01 07:12) [8]

>TStas
Cтепени запоминать не обязательно. Подобный метод возведения в степень реализуется фактически проверкой битов справа налево (так проще, но можно и слева направо, как у тебя) в двоичном представлении показателя степени. Добавлю, что для некоторых степеней (например, n=15) этот метод не самый оптимальный, но очень близок к нему

function FastPower(a, n: Integer): Integer; begin Result := 1; while n > 0 do begin if Odd(n) then begin Dec(n); Result := Result * a; end else begin n := n div 2; a := a * a; end; end; end;

← →
Думкин © (2006-03-01 07:14) [9]

Удалено модератором

← →
grisme © (2006-03-01 07:16) [10]

Имеем X^Y=Z :)
Логарифмируем:
ln (X^Y)=lnZ
lnZ=Y*lnX
Z=exp(Y*lnX) :)

← →
MBo © (2006-03-01 07:26) [11]

>jack128 © (01.03.06 00:53) [5]

Пардон, сразу не обратил внимание на упоминание IntPower, устроенной аналогичным образом.

← →
TUser © (2006-03-01 07:28) [12]

> TStas © (01.03.06 00:30) [3]

Ну да, все правильно. Только в той ветке речь шла про более крутые вещи. Например, в 15 степень ты будешь возводить так

1 - 2 - 4 - 8 - 12 - 14 - 15 " 6 умножений

А можно так

1 - 2 - 3 - 5 - 10 - 15 " 5 умножений

В той ветке пытались найти именно самый оптимальный способ.

← →
TStas © (2006-03-02 19:16) [13]

>jack128 Жень, гадом буду - не знал
>TUser Нет, не так, а как 8+4+2+1
>Думкин Что именно вранье? А с "идиотом" поаккуратнее.

← →
Jeer © (2006-03-02 19:21) [14]

Удалено модератором

← →
TStas © (2006-03-02 19:28) [15]

Удалено модератором

← →
Jeer © (2006-03-02 19:37) [16]

Удалено модератором

← →
TUser © (2006-03-02 20:20) [17]

> >TUser Нет, не так, а как 8+4+2+1

Дык, я тоже самое написал.
1 + 1 = 2
2 + 4 = 4
4 + 4 = 8
8 + 4 = 12
12 + 2 =14
14 + 1 = 15

А можно быстрее
1 + 1 = 2
2 + 2 = 4
4 + 1 = 5
5 + 5 = 10
10 + 5 = 15

В той ветке искался алгоритм отыскания именно самого распрекрасного пути. Если мне память не изменяет. Домой приду - положу сюда свой исходник.

>TUser
Не понял Ваш ответ
>Jeer Неужели я буду тратить ПЛАТНОЕ время на разговор с, по меньшей мере, очень странным человеком? Мне что, заняться больше нечем? Никак в тол не возьму, ну чем Вас так ветка про возведение в степень оскорбила? Если Вам и вправду уже 50 лет, неужели заняться больше нечем?

Удалено модератором

Мои-то посты за что забанили? Мне хамят, я вежливо отвечаю, ну тогда по Ip баньте

Посты не банят, посты удаляют. Я и свой удалил. Просто за офтопик.

>Мне хамят, я вежливо отвечаю, ну тогда по Ip баньте
О, Санта Клаус! Ну и что, что удалили?
Ни первое ни второе здесь не нужно. Удалена только перепалка. По теме ничего не тронуто.

Тады Ой :)

← →
SergP. (2006-03-04 14:51) [25]

> В той ветке пытались найти именно самый оптимальный способ.

Насколько я помню, его нашли...

Кстати, была интересная ветка про возведение в встепень Найти похожие ветки