Appoximating a very large number as a small formula

[NeilNewport]

I want to approximate a very large number in a small way.

I have looked at geometric progression (which I can just about understand), but it seems to only work forwards. I want to supply a very large number and come up with a formula that will represent an approxmation of that number.

The formula needs to be compact and very small.

Somthing like...

2342342134213423423423423213424... (thosands of digits) = 123^45 - 12^12


The object it to have the formula part (i.e. 123^45 - 12^12 ) very small.

I realize that the formula will be an approximation and will be need to have a remainder that is still a very large number. I could then calculate the formula again on the remainder, and so on until I end up with a whole series of formulas and a manageable sized remainder.

Can anyone help me with what I want to do?

 

[Gib Z]

Depends what the number is like. Does it have a pattern? Anything special about it?

 

[NeilNewport]

Depends what the number is like. Does it have a pattern? Anything special about it?

No, nothing special about it, it is however very very big, maybe millions of digits.

 

[Werg22]

well... you can approximate it by considering the first few digits... as in

2342342134213423423423423213424 = ~ 2*10^30 + 3*10^29 + 4*10^28

Otherwise, there exist no simple formula. The number could be a prime, after all.

 

[Crosson]

Modern computers can handle numbers with millions of digits exactly.

If you want a better scheme then the one Werg gave, please tell us more about what you are doing so that we can help preserve the important information in the number.

 

[NeilNewport]

Thanks Werg22, that fasinating.

Here is a bit more meat.

If I choose to find a geometric progression, for example, that was close to the number needed. The only way I see is for me to jump in and calculated progressiivly larger and lager numbers and compared each one until I went bigger then the number I wanted to find, and then I could step back one calculation and use that as being the nearesst without going over.

In other words using poke and hope technolgy.

Is there a more ingelligent way to, for example, use transposition of formula to find something that is close, and then try something different for example a simple power calculation and see if that gets closer, but not over to what I want.

Do you see where I am coming from?

Can I atempt transposition of formula to make wild guesses and see which of a number of methods is the closest. If so, then how would I transpose for example, a geometric progression, given that I know what the result x is.

I really appreciate your kind help.

 

[D H]

This is an NP hard problem (or even harder). Moreover, your search criterion are not well defined. What do you mean by "approximate"? What is your function of merit?

 

[NeilNewport]

Forgive me, but I don't understan the term "function of merit". I am not very good at maths.


Lets use a silly example ...

x = 97651234564312454398547234923469823476349329

Taking this relatively small number as an example


Test 1

lets say that 123 ^ 47 = x - 52342341234 (I know it does not but I don't have a good claculator handy)

So, 123 ^ 47 is close to x, and only missed it by being 52342341234 too small.



Test 2

Let now say that

542233 ^ 12 = x - 23942 (yes, I know it does not, but bear with me)



Test 2 would be a better approximation as the remainder 23942 is smaller than the remainder in test 1


So, I would choose test 2 as being the best approximation.


It there a better way to make more ingelligent gueses at the formula I should use rather and just iterating in incrementing loop up from zero testing each time until I go over x and then step back one iteration, to find the nearest formula below what I want to find.


Please forgive me, but I only undertand simple explanations and do appreciate that I am texting with true maths professors and alike.


Please be gentle, and thanks for all your kind help.

 

[StatusX]

You can't get anything for free. If you want to approximate a 1000 digit number to within a number of, say, 100 digits, this is equivalent to specifying a 900 digit number.

 

[NeilNewport]

Thanks for that StatusX. I get what you are saying.


OK, so I have to be happy to make guesses and do things by poke a hope and iteration, but can you formula transpose for example, a geometric series, if you already have the result of x and give some of the terms needed.

If for example it do this..

6 = x + y

So could find x, if you set y to a test value of 4.

x + 4 = 6

Since we know already that the result is 6, and if you also have y set as 4, then x must be 2. Bingo we know one solution to the whole formula 6 = 4 + 2.

Can someone show me how you would transpose a geometric expression if we set some of the terms, and use clever iterations that we can deduce from the result.

By clever iterations, I mean can we deduce any thing from a number before we start so that we can jump into the iterations as a reasonable point.

For example if we wanted to find 123456, it would not be clever to start at 1 and add 1 to it each time, as it would take 123455 iterations to find 123456.

However, because 123456 is an even number, we could start at 2 and we could add 2 each time and get there in half the time.

Are there any other clever deductions we can make from numbers that would involve powers or other terms rather than simple addition.

I do hope you are still following me.

 

[Gib Z]

Well I would try Prime factorization, seems like the easiest method. We always have the risk of the number being prime, but seeing how long the number is, it probably isn't prime unless specifically chosen for that purpose.

Even if it is prime, just subtract or add a small amount to that number and factorize that number.

 

[d_leet]

Well I would try Prime factorization, seems like the easiest method. We always have the risk of the number being prime, but seeing how long the number is, it probably isn't prime unless specifically chosen for that purpose.

Even if it is prime, just subtract or add a small amount to that number and factorize that number.

A lot of encryption methods would be shot if there were an an easy way to factor large numbers (as in possibly thousands or millions of digits) into primes.

 

[Gib Z]

O I never said that it would be easy :) Perhaps a large computational time yes, but I am assuming the number is less than 10 thousand digits, and its not that bad if it is.

 

[d_leet]

O I never said that it would be easy :) Perhaps a large computational time yes, but I am assuming the number is less than 10 thousand digits, and its not that bad if it is.

http://mathworld.wolfram.com/news/2005-11-08/rsa-640/

Notice in the chart, towards the botton of the page, how two hundred thousand dollars is offered for factoring a 617 digit number, and how it has not yet been done.

 

[Gib Z]

Damn >.< my bad then. I thought someone could do some brute force program to try every number until they got it...Sorry then

 

[NeilNewport]

Thanks for everyones help.

I now think what I am looking for is not really possible or at least not very easy.

Many thanks everyone for putting me right, I won't waste anymore of your time.