Операции с очень-очень большими числами.

Добрый день,

Прошу заранее извинить за возможную нечёткость в постановке вопроса, ибо по профессии мед.-биолог и в программировании разбираюсь слабо, а если честно, то вообще никак.

Но,
возникла задача подобрать решение к А = х**y (** С возведение в степень)
х,y С целые числа
А С  тоже целое число, оно задано в условии.

Основая проблема в том, что А это очень большое число (около 1000 знаков в десятичной системе), а решение должно быть в форме числа, а не 10е25 или другое подобное представление.

Решение (назовём А1) должно по модулю(!) быть наиболее приближенным к А

Можно ли в сети найти подобную программу, да так, чтоб её использование было доступно "чайнику" (где хоть искать-то?)

Если такой программы нет, то является ли её написание сверхсложной задачей или нет? (т.е можно ли подойти к нашим университетским программистам и попросить написать подобное "за бутылку" или это работа на 3 года для лаборатории из 10 человек?)

Заранее благодарен,
Л.

Я уже этим занимался. Если надо, спец. для Вас сделаю и кину скомпиленной прогой. Один вопрос: надо алгоритм или *ТОЛЬКО САМО РЕШЕНИЕ* ?

Я имею ввиду, что это отнимет у меня около часа - и до двух дней при страшном невезении.

Цитата HOMO PROGRAMMATIS, 15.01.03, 22:24:14

Я уже этим занимался. Если надо, спец. для Вас сделаю и кину скомпиленной прогой. Один вопрос: надо алгоритм или *ТОЛЬКО САМО РЕШЕНИЕ* ?

Спасибо за ответ.

Теоретически нужна программа, фунициклирующая на Mac или Win в таком виде, чтоб биолог мог найти куда там цифирки ввести (много циферок  ) которая после введения циферок тихо искала бы решение, блокируя компутер на несколько часов (предполагаю, что это займёт именно столько времени).

Это как бы идеальный случай. Учитывая, что сейчас нет ничего, любой вариант будет с радостью принят, НО

есть ли возможность избежать работы СПЕЦИАЛЬНО ДЛЯ? Мне, право, неловко. Т.е. будет или нет Нобелевская премия, которой можно поделиться, никто не знает , а нагружать Вас дополнительной работой неловко.

Цитата JKG, 15.01.03, 22:39:16

Спасибо за ответ.

Теоретически нужна программа, фунициклирующая на Mac или Win в таком виде, чтоб биолог мог найти куда там цифирки ввести (много циферок  ) которая после введения циферок тихо искала бы решение, блокируя компутер на несколько часов (предполагаю, что это займёт именно столько времени).

Это как бы идеальный случай. Учитывая, что сейчас нет ничего, любой вариант будет с радостью принят, НО

есть ли возможность избежать работы СПЕЦИАЛЬНО ДЛЯ? Мне, право, неловко. Т.е. будет или нет Нобелевская премия, которой можно поделиться, никто не знает , а нагружать Вас дополнительной работой неловко.

так вы зашлите рублей 100 почтовым переводом. зато прога будет на все 100!

Я уже работаю и мало того - почти готово! Чичас интерфейс склепаем и... Результат кину на мыло. Будут малейшие замечания-просьбы - не стесняйтесь, кодить - моё любимое занятие.

СРОЧНО: *Точно* опишите задачу: что дано в условии, что требуется на выходе!!!

Сообщение отредактировано: HOMO_PROGRAMMATIS - 15.01.03, 20:02

я бы на месте биолога все таки кинул рублей сто для приличия.

Цитата EXPERIMENTER, 15.01.03, 23:55:54

я бы на месте биолога все таки кинул рублей сто для приличия.

а я бы не мерил всё деньгами.

Цитата EXPERIMENTER, 15.01.03, 23:55:54

я бы на месте биолога все таки кинул рублей сто для приличия.

Благодарю за подсказку.
Думаю данный вопрос легкоразрешим путем частной переписки с человеком заинтересовавшимся решением проблемы.

Цитата JKG, 16.01.03, 00:03:46

Благодарю за подсказку.
Думаю данный вопрос легкоразрешим путем частной переписки с человеком заинтересовавшимся решением проблемы.

гы. извините. не подумал.

Цитата shadeofgray, 15.01.03, 23:59:29

а я бы не мерил всё деньгами.

но я же не все мерею. на самом деле, это совсем не мое дело. они сами договорятся.

матлаб
лекго справится с вашей проблемой

А как конкретно там это делается? Может я зря этим занялся и всё уже в самом деле готово? Ну вот найдите мне приближение к 987654321987654321987654321123456789?

digits(2000)
dpi(242344444444444444444444444444*44444444444444444444444)

А причём тут собственно умножение?
Может Вы не обратили внимания, но спрашивается про возведение в степень!

Если я просто чего не секу, то приведите в док-во X и Y, такие что X в степени Y максимально близко к приведённому выше числу.

Цитата esperanto, 16.01.03, 15:06:03

digits(2000)
dpi(242344444444444444444444444444*44444444444444444444444)

чего-то я не нашел функции в dpi у себя в версии 6.0

а нашел функцию vpa! рулез!

Сообщение отредактировано: experimenter - 16.01.03, 15:35

Может кто-нить уже ответит делается то что требуется в этом несчастном пакете или нет?

ну, там есть такая функция.
digits(n)
n - какова макс разрядность чисел с которыми оперирует матлаб. а ф-ия
vpa(а) - дает представление числа (те когда число длинное, то вместо 4е45 он покажет все 45 циферек).
я думаю алгоритм все равно реализовывать надо.

В перле есть библиотека, работающая с числами любой длины.
Сам не делал, но можете посмотреть.

Вообще говоря, у меня есть класс, написанный лично мной, который делает эти самые операции... Проблема в самой задаче. Так что разве что если кто-нить видел что её можно где-нить решить, то сообщите.

Цитата HOMO PROGRAMMATIS, 16.01.03, 14:58:04

А как конкретно там это делается? Может я зря этим занялся и всё уже в самом деле готово? Ну вот найдите мне приближение к 987654321987654321987654321123456789?

Если бы интересовало не приближенное решение, а точное то:

Любое натуральное число A можно разложить на простые множители
A = (p1^m1)*(p2^m2)*(p3^m3)*...
где p1,p2,p3,... - простые числа, m1,m2,m3,... - кратности этих простых чисел.
Например
10 000 = (2^4)*(5^4) = (2*5)^4 = 10^4

Значит решение уравнения
A = x^y
При A = 10 000 будет x = 10, y = 4.

При A = 12345 = 3*5*823, ответ тривиальный x = 12345, y = 1

При A = 987654321987654321987654321123456789
= (3^2)*11*29*1039*23371*190839829*74235205371739259
Ответ опять тривиальный x=A, y=1.


У JKG, A - имеет 1000 десятичных знаков, значит задачу разложения A = x^y решать придется очень долго. Однако, стоит только убедиться в том что число А делится на какое-нибудь простое число всего один раз (соответствующая кратность = 1), то отсюда сразу же следует, что существует только тривиальное решение x = A, y = 1. Или если наибольший общий множитель чисел m1,m2,m3,... равен 1, то тоже возможно лишь тривиальное решение. Так как тривиальных решение существует огромное количество, то функция поиска решения, в среднем,  будет работать достаточно быстро.

Но правда, JKG надо найти решение не точно, а приближенно, тут надо подумать...

P.S.
Я пользовался функцией FactorInteger[] из Mathematica 4.1

Сообщение отредактировано: S.Yu.Gubanov - 17.01.03, 14:54

А теперь стоит прочитать задачу внимательно. Нужно найти не собсно решение (его конечно как правило нет), а такие X и Y что они максимально приближаются к А.

+А если А - простое? Понадобится *довольно много* времени, чтобы это понять, а затем понять, что к решению задачи мы не приблизились.

+Причём X и Y не равны 1 (это там не написано, но мне уже сообщили).

Сообщение отредактировано: HOMO_PROGRAMMATIS - 17.01.03, 14:55

Цитата HOMO PROGRAMMATIS, 17.01.03, 17:53:42

А теперь стоит прочитать задачу внимательно. Нужно найти не собсно решение (его конечно как правило нет), а такие X и Y что они максимально приближаются к А.

+А если А - простое? Понадобится *довольно много* времени, чтобы это понять, а затем понять, что к решению задачи мы не приблизились.

+Причём X и Y не равны 1 (это там не написано, но мне уже сообщили).

Извиняюсь, уже поправил текст.

если А простое, то сначала надо проверять тестом на простоту.

слушайте, а если минимизировать функцию
f(x,y) = (A - x^y)^2
типа частные производные. и к нулю их!
df/dx = 2*(A - x^y)(- y*x^(y-1)) = 0
df/dy = 2*(A - x^y)*ln x * x^y    = 0
правда типа числа должны быть целыми, но будет приближение! а это уже что-то!
хотя чего-то А наверное влиять не будет! да, и похоже там максимум будет, а не минимум.

тогда!
просто решать систему уравнений численными методами разумеется!

х^y  = А
x + y = B
B - какое-нить число. второе условие взято с потолка. надо взять такое оттуда, чтобы х>0 и y > 0. вот сие есть мои мысли.

Сообщение отредактировано: experimenter - 17.01.03, 15:38

Вообще, я уже много над этим думал. Что я в итоге напридумывал:

(Здесь [х] - взятие целой части х)

Цикл по показателю степени (Y).
Самое начальное Y = [logA/log2], в цикле Y уменьшается.

Тело цикла:

Цитата

Основание находится (приближённо) в виде [10^(logA/Y)]
Далее перебираем близкие основания (+-5) и ищём лучшее приближение, затем берём след. Y1 = Y - 1

<br>Пусть A = 123456789012345678901234567890 примерно равно 1.23456789012345 * 10^29<br>+Почему 14 знаков после запятой? Это стандартный флоат, для него можно взять логарифм стандартными средствами. <br><br>Тогда logA = log((A/10^29) * 10^29) = log(10^29) * log(A/ 10^29) = 29 + log(A/10^29) примерно равно 29 + log(1.23456789012345) <br>

Такого приближения достаточно для того чтобы искать основания с  ~20 цифрами, но дальше - напряг. Сейчас мылом пытаюсь добиться от автора треда нужны ли ему основания более 20 цифр длиной.

Если у кого есть математические соображения - пишите.

Сообщение отредактировано: HOMO_PROGRAMMATIS - 17.01.03, 15:40

так я вроде написАл. ???

Сорри, но я ни фига не понимаю в том что вы написали. Как конкретно найти эту пару чисел? И сколько времени это займёт?  ;) А вот у меня совершенно конкретное решение как это делать. Если я чего-то не просёк, поясните.

Цитата HOMO PROGRAMMATIS, 17.01.03, 18:44:05

Сорри, но я ни фига не понимаю в том что вы написали. Как конкретно найти эту пару чисел? И сколько времени это займёт?   А вот у меня совершенно конкретное решение как это делать. Если я чего-то не просёк, поясните.

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

Сообщение отредактировано: experimenter - 17.01.03, 15:48

Цитата HOMO PROGRAMMATIS, 17.01.03, 18:39:43

Вообще, я уже много над этим думал. Что я в итоге напридумывал:

(Здесь [х] - взятие целой части х)

Цикл по показателю степени (Y).
Самое начальное Y = [logA/log2], в цикле Y уменьшается.

Я сейчас тоже примерно с этим химичил
Написал такую прогу

A = 987654321987654321987654321123456789;
M1 = 100000;
M2 = 10*M1;
L[n_] := Round[N[Log[n, A]]];
K = Table[L[n], {n, M1, M2}];
P = Abs[A - Table[n^K[[n - M1 + 1]], {n, M1, M2}]];
q = 10^100;
u = -1;
For[i = 1, i < Length[P], i++; {q, u} = If[P[[i]] < q, {P[[i]], i}, {q, u}]; ]
u
N[P[[u]]/A]

Нашел оптимальное выражение

А1 = 997932^6

При этом погрешность равна одной миллионной

(А - 997932^6)/А = - 1.671*10^(-6)


Сейчас думаю вот что:
Малое изменение показателя степени дает очень большие изменения в результат, поэтому показатель степени y = 6 - получился очень маленький.
Значит решать надо перебором по y = 2,3,4,5,6,7,8,9,10,...

x = Log[y, A]

Сообщение отредактировано: S.Yu.Gubanov - 20.01.03, 07:53

Господа, извиняюсь, что гружу своими задачами,

Дело в том, что более полное описание отправлял е-письмом, поэтому некоторые детали здесь, на форуме, недоступны и отюда часть проблем, типа дискуссии о том простое А или нет.
На самом деле задача должна быть сформулирована следующим образом.

Очень большая величина А (целое число из 1000 Ки Кболее знаков) должна быть представлена как

A = х**у +Z

где
** обозначает возведение в степень.
х и у -- целые числа, большие чем 1
х -- меньше 19 знаков (ограничение найденное HOMO PROGRAMMATIS, иначе время исчисления стремится к бесконечности)
Z должно быть по модулю минимально из всех возможных вариантов.

Поэтому совершенно не важно является ли А простым числом. Наличие Z удаляет эту проблему.


Kогда рылся в интернете (искал по словам "big number calculation") нашел Ксайты, где предлагаются алгоритмы для операций с большими числами (ограничения на величину числа вносятся только размером оперативной памяти), но разобраться в них не по зубам было.

http://www.tc.umn.edu/~ringx004/mapm-main.html
http://www.geocities.com/aritonc/download.html
http://world.std.com/~reinhold/BigNumCalc.html
http://www.jonelo.de/java/bigal.html

Kроме того видел упоминание, что класс BigInteger из Java считает числа длиной до ~2млн знаков

Сообщение отредактировано: JKG - 17.01.03, 17:00

Цитата S.Yu.Gubanov, 17.01.03, 18:48:42

Малое изменение показателя степени дает очень большие изменения в результат, поэтому показатель степени y = 6 - получился очень маленький.
Значит решать надо перебором по y = 2,3,4,5,6,7,8,9,10,.

Наверное *простой* перебор займет очень много времени.
Возможно следующее решение проблемы.
На первом этапе найти приближение
х**х = А

если А = 302875106596822 , то это 13**13 + 4569 (Z0) = 302875106592253 + 4569
а дальше плясать от этого, т.е
А = 14**y1 + Z1
А = 12**у2 + Z2
Eсли Z1 или Z2 меньше Z0, то комбинация 12 , у2, Z2 временно, пока не найдется более оптимальное решение, сохраняется.
Возможно будет полезно  ввести дополнительное ограничение, что х+у должна быть минимальной, это исключит варианты очень больших показателей для очень маленьких оснований (типа 2 , 3 итд)

что за привычка решать все перебором? ну, зацените мой подход! может чего-нить из него можно накoвырять?

Сообщение отредактировано: experimenter - 17.01.03, 18:43

Цитата EXPERIMENTER, 17.01.03, 21:42:31

что за привычка решать все перебором? ну, зацените мой подход! может чего-нить из него можно накoвырять?

это насчёт производных? Не получится - при поиске экстремума работать придется на поле вещественных чисел, а там существует бесконечное число возможных x и y, приводящих нас к идеальному решению. А вводить условие нормировки x+y=B - не корректно, т.к. не имеет никакого отношения к оптимальности решения.

Цитата shadeofgray, 18.01.03, 00:22:11

это насчёт производных? Не получится - при поиске экстремума работать придется на поле вещественных чисел, а там существует бесконечное число возможных x и y, приводящих нас к идеальному решению. А вводить условие нормировки x+y=B - не корректно, т.к. не имеет никакого отношения к оптимальности решения.

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

Сообщение отредактировано: experimenter - 18.01.03, 00:26

Цитата EXPERIMENTER, 18.01.03, 03:25:01

перебор при числах длинной офигенной займет Бог знает скоко времени.

Почему Бог знает сколько времени? Ничего подобного. Надо перебрать всего-то
Log[2, A]
вариантов для y.
Вот смотри:
Допустим, что попался самый "худший" случай
A = 2^n
т.е. x= 2, y = n = Log[2, A].
Во всех остальных случаях
x > 2,  
y < Log[2, A].

Надо делать перебор по y = 2,3,4,...,Round(Log(2, A)), т.е. если число A имеет 1000 десятичных знаков, то (Log(2, A) --> 3325) получаем, всего-то три тысячи вариантов для перебора. Разьве это много?

Цитата JKG, 15.01.03, 21:13:08

Добрый день,

Прошу заранее извинить за возможную нечёткость в постановке вопроса, ибо по профессии мед.-биолог и в программировании разбираюсь слабо, а если честно, то вообще никак.



Если такой программы нет, то является ли её написание сверхсложной задачей или нет? (т.е можно ли подойти к нашим университетским программистам и попросить написать подобное "за бутылку" или это работа на 3 года для лаборатории из 10 человек?)

Заранее благодарен,
Л.

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

так что напрасно пытаться что-то выдумать

Цитата JKG, 17.01.03, 19:52:53

Kогда рылся в интернете (искал по словам "big number calculation") нашел Ксайты, где предлагаются алгоритмы для операций с большими числами (ограничения на величину числа вносятся только размером оперативной памяти), но разобраться в них не по зубам было.

http://www.tc.umn.edu/~ringx004/mapm-main.html
http://www.geocities.com/aritonc/download.html
http://world.std.com/~reinhold/BigNumCalc.html
http://www.jonelo.de/java/bigal.html

В довесок
http://algolist.manual.ru/maths/longnum.php

Три дня не мог добраться до форума... Ужас! Всё, задачу мне описали как следует и теперь можно непосредственно этим заняться. Автору треда: только на меня не надейтесь, я могу и подвести - у меня тут сессия и вообще...

Цитата HOMO PROGRAMMATIS, 23.01.03, 21:57:16

Три дня не мог добраться до форума... Ужас! Всё, задачу мне описали как следует и теперь можно непосредственно этим заняться. Автору треда: только на меня не надейтесь, я могу и подвести - у меня тут сессия и вообще...

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

Не будучи математиком, хотел бы всё-таки поделиться некоторыми соображениями.

Если остатки мат. анализа еще не совсем испарились из моей головы, то задача эта имеет какое-то отношение к функциям со многими переменными (х,у,k,Z).
T.e. A = kx**y + Z или f(х,у,k,Z)
учитывая, что необходимо найти min Z, то наверное это будет как-то видно через вторую производную.
Рассуждая по-бытовому, если х и у имеют какое-то значение и оно уже дает больше чем А, то наверное нет смысла варьировать k в большую сторону. То же относится и к х и к у. Таким образом, Z будет достигать минимума только лишь в некоторых точках 4-мерного пространства. Может быть эти точки можно как-то, хотябы приблизительно, описать, а не подбирать эмпирически.  Возможно я сильно ошибаюсь, но к сожалению остатков знаний не хватает, чтобы определиться.
Надо будет залезть в учебники.


С уважением,
Л.

Цитата JKG, 23.01.03, 22:25:00

A = kx**y + Z или f(х,у,k,Z)

А что такое "k"?
Раньше о нем ничего не говорилось.

Цитата JKG, 23.01.03, 22:25:00

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

Не будучи математиком, хотел бы всё-таки поделиться некоторыми соображениями.

Если остатки мат. анализа еще не совсем испарились из моей головы, то задача эта имеет какое-то отношение к функциям со многими переменными (х,у,k,Z).
T.e. A = kx**y + Z или f(х,у,k,Z)
учитывая, что необходимо найти min Z, то наверное это будет как-то видно через вторую производную.
Рассуждая по-бытовому, если х и у имеют какое-то значение и оно уже дает больше чем А, то наверное нет смысла варьировать k в большую сторону. То же относится и к х и к у. Таким образом, Z будет достигать минимума только лишь в некоторых точках 4-мерного пространства. Может быть эти точки можно как-то, хотябы приблизительно, описать, а не подбирать эмпирически.  Возможно я сильно ошибаюсь, но к сожалению остатков знаний не хватает, чтобы определиться.
Надо будет залезть в учебники.


С уважением,
Л.

я конечно извиняюсь но про какие производные вы вообще говорите в поле
ЦЕЛЫХ ЧИСЕЛ
вы думали об это?
тут на лицо задача дискретного программирования если решать её вашим способом
и единственное что пoдходит это тот или иной перебор но у меня никто не слушаеь

снаилучшими

округление тут не поможет ибо не гарантированно гладкие функции

Сообщение отредактировано: esperanto - 24.01.03, 11:37

да, осмыслили. мы тут так сказать идеи нарыть пытались. и хоть и не корректно, но существует округление чисел

Цитата S.Yu.Gubanov, 24.01.03, 10:46:11

А что такое "k"?
Раньше о нем ничего не говорилось.

Виноват, просто там можно ввести поправочный коэффициент, без ущерба для задачи. Это должно всего-навсего слегка уменьшить Z, которое ведь может получить больше чем 2х**у. Вот поэтому я подумал, что в этом случае гораздо проще сразу на это число умножить.
Скажем так: k явилось из упрощения общего вида для случаев когда Z> 2х**у, для остальных случаев k просто будет равно 1
k само-собой тоже целое и само -собой k<х

прикольная тема на самом деле :-)
каждый день обновления читаю! прямо хроники :-)

эксперимента ради написал вчера программку, которая рисует графики
y=a^x, и y=A, + сетку x=1,2,3,...
где А - вводится с клавиатуры, a=1,2,3,...
отметил пересечение этих графиков с сеткой вблизи y=A
думал, что если соединить эти точки, получится монотонная функция. облом :-(
однако
каждый график при увеличении a пересекается с x=1,2,3,... всё выше и выше :-)
d = (a+1)^x-a^x
правда это через одно место, но если найти способ быстрого подсчёта d, то:
] f(a,x) = (a+1)^x-a^x

z0=A;x0=2;a0=2;
for (x=x0;x<=x_max;x++)
{
  k0=a0^x;k=k0;a=a0;
  while(k<=A)
  {
      d = f(a,x);
      k+=d;
      a++;
   };
   z = |A-k|;
   if (z==0) { return (_x=a,_y=x); };
   if (z<z0) { z0=z; _x=a; _y=x; };
};

return (_x, _y);

вот :-)
и вообще. чем плох такой вариант -
_a0 = A^(1/x)
a0 = [_a0]
a1 = a0-1
a2 = a0+1
z1 = |A-a1^x|
z2 = |A-a2^x|
2<=x<=[log2(A)]+1
и просто ищем минимум из всех z1,z2 :-)

Цитата DEiL, 25.01.03, 20:28:19

прикольная тема на самом деле :-)
каждый день обновления читаю! прямо хроники :-)

эксперимента ради написал вчера программку, которая рисует графики
y=a^x, и y=A, + сетку x=1,2,3,...
где А - вводится с клавиатуры, a=1,2,3,...
отметил пересечение этих графиков с сеткой вблизи y=A
думал, что если соединить эти точки, получится монотонная функция. облом :-(
из всех z1,z2 :-)

выше написано ф-я не гладкая

так что не облом а закономерность и