Вычисление С в степени N с минимальным количеством умножений

← →
Студент:( (2005-09-24 01:28) [0]

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

(естесно не в таком виде, с if, for и самым простым я знаком)

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

← →
Германн © (2005-09-24 01:47) [1]

Я лично не понял связку "D6 в сабже" и "минимальное число операций умножения". Причем нет никаких упоминаний об ASM?

Хотя, кто их знает! Нынешних преподов т.е.!

Да! Хотя еще неизвестно о каком предмете универа идет речь.
Я то об алгоритмах программирования.

← →
Lamer@fools.ua © (2005-09-24 01:55) [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;

← →
incolex © (2005-09-24 22:50) [3]

// Lamer@fools.ua © (24.09.05 01:55) [2]

Ты конечно хитрец :-) но зачемже пудрить мозги человеку, зачем расписывать существующую функцию {IntPower (X: Extended; Y: Integer ): Extended;} (хотя в Delphi она написана на ASM), кстати эта ф-ция возводит число только в цлочисленную степень, а вот к примеру, {Power ( X, Y: Extended ): Extended;} - возводит вдробную степень.

← →
jack128 © (2005-09-24 22:57) [4]

Без единого умножения
Result := Exp(Ln(C)*abs(N));
if N < 0 then
Result := 1 / Result;

← →
Lamer@fools.ua © (2005-09-24 23:30) [5]

>>jack128 © (24.09.05 22:57) [4]

Обманывать нехорошо. Во-первых, формально одно умножение есть. Во-вторых, фактически их больше. Логарифм и экспонента, конечно, сопроцессором считаются, только ему их ещё тоже вычислить надобно. И там будет далеко не одно умножение.

← →
Германн © (2005-09-25 01:08) [6]

2 Lamer@fools.ua © (24.09.05 23:30) [5]
> только ему их ещё тоже вычислить надобно. И там будет далеко не одно умножение.

Но причем тут "студент", которому "препод" задал задачку в "универе"?

Имхо, скорее всего тут "задачка для паскаля без дополнительных библиотек". Хотя опять же имхо, можно было бы придумать более "жизненноважную" задачу. Наверняка в "уроках Юрия Зотова" были схожие задачи!

← →
Lamer@fools.ua © (2005-09-25 01:38) [7]

>>Германн © (25.09.05 01:08) [6]

Поясните глубину мысли в использовании экспоненты и логарифма с целью вычислить значение целого числа, возведённого в целую степень.

← →
jack128 © (2005-09-25 01:56) [8]

Lamer@fools.ua © (24.09.05 23:30) [5]
Логарифм и экспонента, конечно, сопроцессором считаются, только ему их ещё тоже вычислить надобно. И там будет далеко не одно умножение. Ну знаешь, мне кажется что сопрцессор не "умножает", а выставляет уровни напряжения на дорожках или что у него там есть ;)
В любом случае молжно так модифицировать твой код(для целых чисел)

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;

← →
Германн © (2005-09-25 02:10) [9]

2 Lamer@fools.ua © (25.09.05 01:38) [7]
>Поясните глубину мысли в использовании экспоненты и логарифма с целью вычислить значение целого числа, возведённого в целую степень.

А где и когда я об этом говорил?
Или ты меня с кем-то спутал?

← →
Lamer@fools.ua © (2005-09-25 02:18) [10]

>>Германн © (25.09.05 02:10) [9]

Фраза, процитированная в [6] относится именно к логарифму и экспоненте.

Я, честно говоря, вообще слабо понял, как [6] относится к вопросу автора топика.

>>jack128 © (25.09.05 01:56) [8]

> Ну знаешь, мне кажется что сопрцессор не "умножает", а выставляет уровни напряжения на дорожках или что у него там есть ;)

Как именно процессор умножает не имеет значения, за исключением случая, когда используются табличные заранее рассчитанные данные.

← →
jack128 © (2005-09-25 02:19) [11]

а ну да, со мной и спутал наверно. Глубина моей мысли была заключена в постановки задачи - функция должна использовать
Студент:( (24.09.05 1:28)
минимальное число операций умножения

Если будет еще менее одекватная постановка задачи, так я рожу еще более "глубокую" мысль ;)

← →
TStas © (2005-09-25 02:21) [12]

А при вычислении корня используется деление, которое по затратности вообще с умножением и сравнивать нельзя

← →
Lamer@fools.ua © (2005-09-25 02:34) [13]

>>jack128 © (25.09.05 02:19) [11]

Чтобы прекратить бессмысленный спор, будем считать, что у меня был внезапный приступ телепатии. Идёт?

← →
Германн © (2005-09-25 02:38) [14]

2 jack128 © (25.09.05 02:19) [11]
Не Жень. Имхо он не спутал, а смешал в кашу все ответы после своих!
И уже дальше отвечал на свои глюки. :)

2 Lamer@fools.ua ©
При чем тут "сопроцессор"? В учебной задаче?

Жень! Ну все-таки "а"декватная!
Я, конечно понимаю, что каждый стремиться достичь уровня АП! Но не такими же способами! :)

← →
Manufel (2005-09-25 17:23) [15]

См http://delphimaster.net/view/1-1127510896/

А на мой взгляд лучшее решение здесь: Lamer@fools.ua © (24.09.05 01:55) [2]

А вот использование Exp и Ln
здесь совершенно не к чему, возводится то целое число в целую степень, а вот Ln и Exp вычисляется С ОЧЕНЬ БОЛЬШИМ количеством умножений
Если кто не знает Ln и Exp вычисляются по формуле ряда Тейлора
e^x=E( (x^n)/x!)
Где Е() - сигма, х! - факториал х, а n>=0, то есть у нас получается бесконечный числовый ряд(иначе можно записать e^x=1+x+(x^2)/2+(x^3)/6 и т.д.), который обрезается в компьютере до некоторой степени, достаточной для очень маленького приближения
Для логарифма ситуация та же

← →
Manufel (2005-09-25 17:23) [16]

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

← →
Manufel (2005-09-25 17:23) [17]

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

Manufel (25.09.05 17:23) [15]
Если кто не знает Ln и Exp вычисляются по формуле ряда Тейлора
Если ты не знаешь, для точного вычисления с большой скоростью ряд Тэйлора мало пригоден. Для вычисления ln, exp, sin, cos используются более сложные методы.

← →
Manufel (2005-09-25 18:56) [19]

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

← →
пятиклассник (2005-09-25 21:21) [20]

:))
procedure TForm1.ButtonCalculateClick(Sender: TObject); begin EditResult.Text := FloatToStr(Exponentation(StrToInt(EditNumber.Text), (StrToInt(EditDegree.Text)))); end; function TForm1.Exponentation(n, d: Integer): Currency; var i,k: Integer; tmp1,tmp2: Int64; begin if d = 0 then begin Result := 1; Exit; end; tmp1 := n; for i := 2 to Abs(d) do begin tmp2 := 0; for k := 1 to n do begin tmp2 := tmp2 + tmp1; end; tmp1 := tmp2; end; if d < 0 then Result := 1/tmp1 else Result := tmp1; end;

← →
пятиклассник (2005-09-25 21:23) [21]

Забыл добавить - операций умножения совсем нету :))

← →
Some (2005-09-25 22:28) [22]

пятиклассник (25.09.05 21:23) [21]

а главное - приложение консольное...

← →
пятиклассник (2005-09-25 22:32) [23]

> Some (25.09.05 22:28) [22]

О боже!
А что, эту функцию нельзя будет использовать в консольном приложении? Она же чиста от VCL, а выше - это только пример использования ;)

← →
пятиклассник (2005-09-26 08:52) [24]

В [20] с ошибочкой. Вот исправленный вариант:)
function TForm1.Exponentation(n, d: Integer): Currency; var i,k: Integer; tmp1,tmp2: Int64; begin if d = 0 then begin Result := 1; Exit; end; tmp1 := Abs(n); for i := 2 to Abs(d) do begin tmp2 := 0; for k := 1 to Abs(n) do begin tmp2 := tmp2 + tmp1; end; tmp1 := tmp2; end; if d < 0 then Result := 1/tmp1 else Result := tmp1; if (n < 0) and (d mod 2 <> 0) then Result := -Result; end;

Вычисление С в степени N с минимальным количеством умножений Найти похожие ветки