Математическое представление больших чисел?

Question

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

Простой математики, я имею в виду только номера с +, -, *, /,^ и () по мере необходимости.

'4^25+2^32' = giveMeMath(1125904201809920); // example

Любой язык будет делать. Я могу реорганизовать его, просто ищу помощь в логике.

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

Update: уточнить, все входные значения будут положительные целые числа (без десятичной точки)

Answer 1

Вот моя попытка в Python:

def give_me_math(n): 

    if n % 2 == 1: 
     n = n - 1 # we need to make every odd number even, and add back one later 
     odd = 1 
    else: 
     odd = 0 
    exps = [] 

    while n > 0: 
     c = 0 
     num = 0 
     while num <= n/2: 
      c += 1 
      num = 2**c 

     exps.append(c)  
     n = n - num 
    return (exps, odd) 

Результаты:

>>> give_me_math(100) 
([6, 5, 2], 0) #2**6 + 2**5 + 2**2 + 0 = 100 

>>> give_me_math(99) 
([6, 5, 1], 1) #2**6 + 2**5 + 2**1 + 1 = 99 

>>> give_me_math(103) 
([6, 5, 2, 1], 1) #2**6 + 2**5 + 2**2 + 2**1 + 1 = 103 

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

Edit:

Результат: Рассчитывает примерно на одну секунду.

>>> give_me_math(10**100 + 3435) 
([332, 329, 326, 323, 320, 319, 317, 315, 314, 312, 309, 306, 304, 303, 300, 298, 295, 294, 289, 288, 286, 285, 284, 283, 282, 279, 278, 277, 275, 273, 272, 267, 265, 264, 261, 258, 257, 256, 255, 250, 247, 246, 242, 239, 238, 235, 234, 233, 227, 225, 224, 223, 222, 221, 220, 217, 216, 215, 211, 209, 207, 206, 203, 202, 201, 198, 191, 187, 186, 185, 181, 176, 172, 171, 169, 166, 165, 164, 163, 162, 159, 157, 155, 153, 151, 149, 148, 145, 142, 137, 136, 131, 127, 125, 123, 117, 115, 114, 113, 111, 107, 106, 105, 104, 100, 11, 10, 8, 6, 5, 3, 1], 1) 

800 цифра работает слишком быстро:

>>> give_me_math(10**800 + 3452) 

Но выход слишком долго, чтобы разместить здесь, что ФОС относятся конечно.

Сложность времени здесь 0 (ln (n)), поэтому она довольно эффективна.

Answer 2

В Java, вы должны смотреть на BigDecimal класса в пакете java.math.

Answer 3

Я предлагаю вам взглянуть на

1. GMP The библиотеке (ГНУ Multiple Precision Арифметика Library) для выполнения арифметика

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

   • Integer factorization (PDF) по Daniel Bernstein Университета штата Иллинойс
   • Integer Factorization Algorithms (PDF) по Connelly Barnes кафедры физики в Университете штата Орегон

Answer 4

Я думаю, что вся проблема может быть переделана в проблему run-length encoding в двоичном представлении длинного целого числа.

Для примера возьмем следующий номер:

17976931348623159077293051907890247336179769789423065727343008115773 
26758055009631327084773224075360211201138798713933576587897688144166 
22492847430639474110969959963482268385702277221395399966640087262359 
69162804527670696057843280792693630866652907025992282065272811175389 
6392184596904358265409895975218053120L 

Это выглядит довольно ужасающим. В двоичной форме:

>>> bin(_) 
'0b11111111111111111111111111111111111111111111111111111111111111111 
11111111111111111111111111111111111111111111111111111111111111111111 
11111111111111111111111111111111111111111111111111111111111111111111 
11111111111111111111111111111111111111111111111111111111111111111111 
11111111111111111111111111111111111111111111111111111111111111111111 
11111111111111111111111111111111111111111111111111111111111111111111 
11111111111111111111111111111111111111111111111111111111111111111111 
11111111111111111111111111111111111111100000000000000000000000000000 
00000000000000000000000000000000000000000000000000000000000000000000 
00000000000000000000000000000000000000000000000000000000000000000000 
00000000000000000000000000000000000000000000000000000000000000000000 
00000000000000000000000000000000000000000000000000000000000000000000 
00000000000000000000000000000000000000000000000000000000000000000000 
00000000000000000000000000000000000000000000000000000000000000000000 
00000000000000000000000000000000000000000000000000000000000000000000 
0000000' 

Это около 500 единиц, а затем 500 нулей. Это предполагает выражение, подобное:

2**1024 - 2**512 

Вот как я получил большое количество в первую очередь.

Если в двоичном представлении целого числа не существует значительных длительных прогонов, это совсем не сработает. 101010101010101010.... - худший случай.