Х в N степени

← →
Студент :((( (2005-10-04 23:35) [0]

Здраствуйте!
Я уже задавал этот вопрос, но ... алгоритм который мне подсказали оказался не самым оптимальным

Мне необходимо реализовать программу в которую вводится 2 целых числа C и N
необходимо вычислить С в степени N используя минимальное число операций умножения
Если не совсем ясно высказался:
Если c=2 n=7
то лучшее это
c:=c*c;
c:=c*c;
c:=c*c;
c:=c/2;
(естесно не в таком виде, с if, for и т.д. я знаком)

Вот та ветка http://delphimaster.net/view/1-1127510917/

Такой вариант решения
function IntPower(X: Cardinal; Y: Cardinal): Int64;
begin
Result := 1;
while Y > 0 do
begin
while not Odd(Y) do
begin
Y := Y div 2;
X := Round(X / (1/ X))
end;
Dec(Y);
Result := Round(Result / (1 / X));
end;
end;
преподаватель забраковал для n=15
оптимально сделать так
x:=xi*xi; 2я степень
x:=x*x; 4я
x:=x*xi; 5я
x:=x*x*x;15 я
Где xi исходное значение Х
Решение в пять операций умножения
Алгоритм написаный выше делает в 8

Так что вновь прошу вашего совета...
Помогите пожалуйста

← →
Fenik © (2005-10-04 23:38) [1]

Преподаватель нам задание дал что ли?

← →
Студент :((( (2005-10-04 23:39) [2]

Сорри вот тот алгоритм который я использовал
function IntPower(X: Cardinal; Y: Cardinal): Int64;
begin
Result := 1;
while Y > 0 do
begin
while not Odd(Y) do
begin
Y := Y div 2;
X := Sqr(X);
end;
Dec(Y);
Result := Result * X;
end;
end;

← →
Студент :((( (2005-10-04 23:40) [3]

Я извиняюсь, но я сам не разбираюсь в этом, да оно мне и не нужно, я студент ФИОЛОГИЧЕСКОГО факультета, а програмирование вообще непонятно зачем нам дали

← →
Anatoly Podgoretsky © (2005-10-04 23:45) [4]

У вас в институте должен быть коператив по написанию курсовых и других работ.

← →
Fenik © (2005-10-04 23:52) [5]

> [3] Студент :((( (04.10.05 23:40)

Если филолог, то математику категорически запрещено знать?
Ущербно как-то :)

← →
Студент :((( (2005-10-05 00:08) [6]

Очень прошу, помогите с алгоритмом... от рассуждений про то что надо знать математику, я её не выучу, а программу уже послезавтра надо сдавать :(

← →
Студент :((( (2005-10-05 00:43) [7]

Эххххх :(

← →
GrayFace © (2005-10-05 04:20) [8]

Fenik © (04.10.05 23:52) [5]
Если филолог, то математику категорически запрещено знать?
А при чем тут математика?

← →
GrayFace © (2005-10-05 04:34) [9]

Студент :((( (04.10.05 23:35)
c:=c/2;
Причем тут 2?

Студент :((( (04.10.05 23:35)
Алгоритм написаный выше делает в 8
7.

Пока нет идей, разве что разложение на простые множители. Но это оптимальностью и не пахнет.

← →
SergP. (2005-10-05 05:00) [10]

> Студент :((( (04.10.05 23:35)

Самое плохое здесь то что задача изначально является тупой. Ведь если искать самый оптимальный способ возведения в степень с минимумом умножений, то можно потратить куда более ресурсов на сами поиски этого способа...

← →
SergP. (2005-10-05 05:21) [11]

> Пока нет идей, разве что разложение на простые множители.
> Но это оптимальностью и не пахнет.

Идея есть одна, но это тоже не совсем оптимально....

Просто до сих пор мы рассматривали поиск оптимального решения методом "деления на 2"
т.е. типа X^14 = (X^7)*(X^7)

это будет не самый оптимальный вариант. Нужно рассмотреть деление степени на оба ближайших к e числа, т.е. 2 и 3

Типа берем N
Если делится на 2 то n = n/2 + n/2
иначе если делится на 3 то n=n/3+n/3+n/3
иначе n=(n-1) +1

← →
SergP. (2005-10-05 05:22) [12]

← →
Virgo_Style © (2005-10-05 06:45) [13]

Студент :((( (04.10.05 23:35)
преподаватель забраковал для n=15

imho тут начинает пахнуть ИИ. Для n=15 - один алгоритм, n=16 - другой, для малых n оптимально решение "в лоб"...

Вообще первым делом надо сформулировать алгоритм решения, пример которого тебе дал преподаватель.

← →
GrayFace © (2005-10-05 07:46) [14]

Например, так:
function StupidPower(X: Cardinal; Y: Cardinal): Int64; var i,j,k:cardinal; begin i:=y mod 2; while i=0 do begin x:=x*x; y:=y div 2; i:=y mod 2; end; if y=1 then exit; i:=y mod 3; while i=0 do begin x:=x*x*x; y:=y div 3; i:=y mod 3; end; if y=1 then exit; i:=y mod 5; while i=0 do begin j:=x*x; x:=x*j*j; y:=y div 5; i:=y mod 5; end; if y=1 then exit; i:=y mod 7; while i=0 do begin j:=x*x; j:=j*j; x:=x*j; y:=y div 7; i:=y mod 7; end; if y=1 then exit; и т.д. (для всех простых чисел до 31) end;

← →
Babay © (2005-10-05 07:48) [15]

а может стоит глянуть как это делает дядюшка Борланд?
из модуля Math

function IntPower(const Base: Extended; const Exponent: Integer): Extended; asm mov ecx, eax cdq fld1 { Result := 1 } xor eax, edx sub eax, edx { eax := Abs(Exponent) } jz @@3 fld Base jmp @@2 @@1: fmul ST, ST { X := Base * Base } @@2: shr eax,1 jnc @@1 fmul ST(1),ST { Result := Result * X } jnz @@1 fstp st { pop X from FPU stack } cmp ecx, 0 jge @@3 fld1 fdivrp { Result := 1 / Result } @@3: fwait end;

function Power(const Base, Exponent: Extended): Extended; begin if Exponent = 0.0 then Result := 1.0 { n**0 = 1 } else if (Base = 0.0) and (Exponent > 0.0) then Result := 0.0 { 0**n = 0, n > 0 } else if (Frac(Exponent) = 0.0) and (Abs(Exponent) <= MaxInt) then Result := IntPower(Base, Integer(Trunc(Exponent))) else Result := Exp(Exponent * Ln(Base)) end;

Выделенная строка Вас и должна заинтересовать, минимум действий. Но конечно нужны проверки ....
На деюсь это то что Вам нужно. ;-)

← →
12DFBDD (2005-10-05 07:57) [16]

Calculates the log of X for a specified base.

Unit

Math

Category

Arithmetic routines

Delphi syntax:

function LogN(const Base, X: Extended): Extended;

C++ syntax:

extern PACKAGE Extended __fastcall LogN(const Extended Base, const Extended X);

Description

LogN returns the log base Base of X.

В Паскале для этой задачи использовали функцию Log() вспомни математику по логарифмам и задача решается с пол пинка

зы
Препод не Боржум?
Если он тебе повезло!!!

← →
GrayFace © (2005-10-05 08:40) [17]

Ой, я ступил.
var SimpleNums: array[0..1000] of Cardinal; // простые числа - инициализируется заранее function StupidPower(X: Cardinal; Y: Cardinal): Int64; var i,j:cardinal; begin Result:=x; for j:=0 to high(SimpleNums) do begin i:=y mod j; while i=0 do begin Result:=IntPower(Result, i); y:=y div j; i:=y mod j; end; if y=1 then exit; end; Result:=IntPower(Result,y); end;

Это алгоритм того, что хочет препод, если не считать mod за операцию. :)

← →
SergP. (2005-10-05 09:15) [18]

> и т.д. (для всех простых чисел до 31)
> end;

Да не нужно для всех простых чисел... ИМХО достаточно для 2 и 3

Почитайте Agner Fog.

SergP. (05.10.05 9:15) [18]
Да не нужно для всех простых чисел... ИМХО достаточно для 2 и 3
25=5*5
5=4+1 - 3 операции
Итого 4 операции

25=16+8+1
16+8+1 - 6 операций (4 на "16" и 2 "+")

Так что 5 тоже надо проверять.

Проглючил. 5*5 - тоже 6 операций

Тогда 125.
125=5*5*5
5=4+1 - 3 операции
Итого 9 операций.

125=64+32+16+8+4+1 - 6+5=11 операций.

Вот всего две функции и одна операция умножения:

c:=Exp(n*Ln(c));

Работает безотказно.

> Работает безотказно.

Не только безотказно но и круглосуточно.

← →
SergP. (2005-10-07 04:32) [25]

> SergProger © (07.10.05 01:05) [23]
> Вот всего две функции и одна операция умножения:
>
> c:=Exp(n*Ln(c));
>
> Работает безотказно.

Спасибо. Но для сабжа это не подходит... Читайте условие.

Х в N степени Найти похожие ветки