Бесконечно большие числа
У меня есть задачка: написать калькулятор, который бы работал с числами любых размеров. То есть, размер числа должен быть ограничен не размерами переменной типа [FONT="Courier New"]Real[/FONT], а, скажем, объёмом оперативной памяти. Действий всего пять: сложение, умножение, вычитание, деление и возведение в произвольную степень (включая дробные и отрицательные). Я начал реализовывать сложение методом "в столбик", то есть как этом учат во втором классе. Для этого я сохраняю введённые числа в строку (пишу на Delphi, насколько знаю, у них длина строки как раз ограничена объёмом ОП), потом вырезаю по одной цифре, складываю, и записываю в третью строку. В принципе то же можно проделать с вычитанием, с грехом пополам с умножением и с большим гемором для деления. Но вот на произвольной степени дело останавливается... Посоветуйте, пожалуйста, что тут можно сделать?
P.S. Если что, то это БДЗ по информатике на первом курсе в МИФИ, факультет Б.
P.S. Если что, то это БДЗ по информатике на первом курсе в МИФИ, факультет Б.
Для целочисленного возведения достаточно просто n раз вызвать функцию умножения :D
А про дробное ничего не скажу :(
А про дробное ничего не скажу :(
[QUOTE=Валериус] Для этого я сохраняю введённые числа в строку (пишу на Delphi, насколько знаю, у них длина строки как раз ограничена объёмом ОП), потом вырезаю по одной цифре, складываю, и записываю в третью строку. В принципе то же можно проделать с вычитанием, с грехом пополам с умножением и с большим гемором для деления. Но вот на произвольной степени дело останавливается... Посоветуйте, пожалуйста, что тут можно сделать?
[/QUOTE]
Алгоритм правельный, надо выполнять действия поразрядно, и при необходимости выполнять перенос в старший разряд. Но лучше это выполнять в двоичной системе счисления, проще. А со степенью вообще просто: надо выполнять умножение на само себя n-1, где n - степень.
Т.е. запоминаешь исходное число в переменной А, а результат умножения в Б, и умнажаешь А на Б еще n-2 раза.
[/QUOTE]
Алгоритм правельный, надо выполнять действия поразрядно, и при необходимости выполнять перенос в старший разряд. Но лучше это выполнять в двоичной системе счисления, проще. А со степенью вообще просто: надо выполнять умножение на само себя n-1, где n - степень.
Т.е. запоминаешь исходное число в переменной А, а результат умножения в Б, и умнажаешь А на Б еще n-2 раза.
[QUOTE=Deeoni$]А со степенью вообще просто: надо выполнять умножение на само себя n-1, где n - степень.[/QUOTE]Инересно, как ты собираешься умножить число само на себя, скажем.... -2/3 раз :))
Общая формула возведения в степень выражается через натуральный логарифм и экспоненту. А они уже вычисляются через разложение в ряд Тейлора с определенной точностью (надеюсь я ничего не перепутал). Ну а ряд Тейлора - это реализованные уже четыре операции.
2Валериус: Действительно, ты добьешься большей производительности, если реализуешь работу напрямую с двоичными числами (лучше всего с ассемблерными вставками, но можно и на чистой делфе, если не знаешь ассемблера). Когда-то писал класс для реализации похожей функциональности на олимпиаде на 1-м курсе за пару часов... Правда без степени :)
Общая формула возведения в степень выражается через натуральный логарифм и экспоненту. А они уже вычисляются через разложение в ряд Тейлора с определенной точностью (надеюсь я ничего не перепутал). Ну а ряд Тейлора - это реализованные уже четыре операции.
2Валериус: Действительно, ты добьешься большей производительности, если реализуешь работу напрямую с двоичными числами (лучше всего с ассемблерными вставками, но можно и на чистой делфе, если не знаешь ассемблера). Когда-то писал класс для реализации похожей функциональности на олимпиаде на 1-м курсе за пару часов... Правда без степени :)
[QUOTE=Валериус]У меня есть задачка: написать калькулятор, который бы работал с числами любых размеров. То есть, размер числа должен быть ограничен не размерами переменной типа [FONT="Courier New"]Real[/FONT], а, скажем, объёмом оперативной памяти.[/QUOTE]
Стоит только немного поискать - и в дебрях инета найдутся готовые математические библиотеки, уже реализовавшие математические действия для "больших" чисел. Я, по крайней мере, встречался с упоминаниями таковых на С++. Просто перепиши на дельфи.
Стоит только немного поискать - и в дебрях инета найдутся готовые математические библиотеки, уже реализовавшие математические действия для "больших" чисел. Я, по крайней мере, встречался с упоминаниями таковых на С++. Просто перепиши на дельфи.
To sergey40a & el scorpio.
Вообще, число в произвольной действительной степени в математике определяется как предел последовательности рациональных степеней числа при том условии, что последовательность степеней стремится к требуемому числу :) Поскольку программисты с последовательностями работать не умеют :),
a^x = e^(ln a * x);
экспонента определяется рядом Тейлора
e^x = 1+x+(x^2 / 2) + (x^3 / 3!) + ... + (x^n / n!),
где n выбирается в зависимости от требуемой точности.
Вообще, число в произвольной действительной степени в математике определяется как предел последовательности рациональных степеней числа при том условии, что последовательность степеней стремится к требуемому числу :) Поскольку программисты с последовательностями работать не умеют :),
a^x = e^(ln a * x);
экспонента определяется рядом Тейлора
e^x = 1+x+(x^2 / 2) + (x^3 / 3!) + ... + (x^n / n!),
где n выбирается в зависимости от требуемой точности.
[QUOTE=sergey40a]Инересно, как ты собираешься умножить число само на себя, скажем.... -2/3 раз :))
[/QUOTE]
по дефаулту подумал что степень натуральное число
[/QUOTE]
по дефаулту подумал что степень натуральное число
использую ряд тейлора можно возвести в любую степень.
[QUOTE=sergey40a]Действительно, ты добьешься большей производительности, если реализуешь работу напрямую с двоичными числами (лучше всего с ассемблерными вставками, но можно и на чистой делфе, если не знаешь ассемблера). Когда-то писал класс для реализации похожей функциональности на олимпиаде на 1-м курсе за пару часов... Правда без степени :)[/QUOTE]
А можешь поделиться этим исходником? :) Или хотя бы дать ссылку, где можно про работу с двоичными числами в дельфе почитать?
А можешь поделиться этим исходником? :) Или хотя бы дать ссылку, где можно про работу с двоичными числами в дельфе почитать?
Сложени проще реализовать следующим способом. Число храницца в строковом формате. Так что вырезаем последние 9 цифр. Тогда их сумма никак не превысит 2147483647, т.е. в Int32 влезим. Дальше понятно...
Со степенью могу подсказать следующее:
1) Нецелую только через логарифм и ряд Тейлора.
2) А вот в целую возводить лучьше так:
возьмем для примера x^23. Можно представить это в виде:
x^23 = x*y^2; y = x^11 = x*z^2; z = x^5 = x*(q)^2; q = x^2; Всего 10 умножений вместо 23! Правда с точки зрения использования памяти нерационально.
Есть еще более крутой метод. И с памятью там получьше в несколько раз. Только вот с ходу не вспомню. Если изъявите желание, то потом изложу...
Со степенью могу подсказать следующее:
1) Нецелую только через логарифм и ряд Тейлора.
2) А вот в целую возводить лучьше так:
возьмем для примера x^23. Можно представить это в виде:
x^23 = x*y^2; y = x^11 = x*z^2; z = x^5 = x*(q)^2; q = x^2; Всего 10 умножений вместо 23! Правда с точки зрения использования памяти нерационально.
Есть еще более крутой метод. И с памятью там получьше в несколько раз. Только вот с ходу не вспомню. Если изъявите желание, то потом изложу...
Может, это не совсем то что нужно, но может кому-нибудь пригодится. У меня есть небольшой пример на Delphi работы с очень большими (по порядку величины) целыми числами. Демонстрируется лишь сам принцип - разделение числа на значущую часть и порядок. Адрес: http://sadovoya.narod.ru/BIG_NUMBERS.ZIP
вот ссылка http://algolist.manual.ru/maths/longnum.php там есть все что тебе нужно
Спасибо, AUMN. Очень интересный сайт по Вашей ссылке. Кроме больших чисел я нашел там еще много интересного. Советую всем взглянуть.