Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Прочее";
Текущий архив: 2006.03.26;
Скачать: [xml.tar.bz2];

Вниз

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

 
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

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


 
TStas ©   (2006-03-02 22:12) [18]

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


 
LordOfRock ©   (2006-03-03 00:05) [19]

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


 
TStas ©   (2006-03-03 00:28) [20]

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


 
McSimm ©   (2006-03-03 00:38) [21]

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


 
TStas ©   (2006-03-04 00:45) [22]

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


 
McSimm ©   (2006-03-04 01:08) [23]

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

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


 
TStas ©   (2006-03-04 13:56) [24]

Тады Ой :)


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


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


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



Страницы: 1 вся ветка

Форум: "Прочее";
Текущий архив: 2006.03.26;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.5 MB
Время: 0.046 c
2-1142260999
Митяй
2006-03-13 17:43
2006.03.26
Иерархические данные


4-1135390132
Grinder
2005-12-24 05:08
2006.03.26
Добавить пункт в чужое меню


15-1141577737
Vendict
2006-03-05 19:55
2006.03.26
Linux + GPRS


1-1140919693
Grol
2006-02-26 05:08
2006.03.26
Быстро обновить все визуальные компонент на форме


2-1141923333
Fenix
2006-03-09 19:55
2006.03.26
Преобразование TCaption в Pchar





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский