Mathematical representation of large numbers?

Question

I am attempting to write a function which takes a large number as input (upwards of 800 digits long) and returns a simple formula of no complex math as a string.

By simple math, I mean just numbers with +,-,*,/,^ and () as needed.

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

Any language would do. I can refactor it, just looking for some help with the logic.

Bonus. The shorter the output the better. Processing time is important. Also, mathematical accuracy is a must.

Update: to clarify, all input values will be positive integers (no decimals)

Answer 1

I think the entire problem can be recast to a run-length encoding problem on the binary representation of the long integer.

For example, take the following number:

17976931348623159077293051907890247336179769789423065727343008115773
26758055009631327084773224075360211201138798713933576587897688144166
22492847430639474110969959963482268385702277221395399966640087262359
69162804527670696057843280792693630866652907025992282065272811175389
6392184596904358265409895975218053120L

This looks fairly horrendous. In binary, though:

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

Which is about 500 ones, followed by 500 zeroes. This suggests an expression like:

2**1024 - 2**512

Which is how I obtained the large number in the first place.

If there are no significantly long runs in the binary representation of the integer, this won't work well at all. 101010101010101010.... is the worst case.

Answer 2

Here is my attempt in 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)

Results:

>>> 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

I believe the results are accurate, but I am not sure about your other criteria.

Edit:

Result: Calculates in about a second.

>>> 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 digit works fast too:

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

But the output is too long to post here, which is OPs concern of course.

Time complexity here is 0(ln(n)), so it is pretty efficient.

Answer 3

I'd suggest you to have a look at

1. The GMP library (The GNU Multiple Precision Arithmetic Library) for performing the arithmetics

2. Take a look at integer factorization. The link redirects to Wikipedia which should give probably a good overview. However to be a bit more scientific:

   • Integer factorization (PDF) by Daniel Bernstein of the University of Illinois
   • Integer Factorization Algorithms (PDF) by Connelly Barnes of the Department of Physics, Oregon State University

Answer 4

In java, you should take a look at the BigDecimal class in java.math package.