Big Numbers (Base 256)

Hullo hullo,

If I wanted to manipulate: 72057594037927936

That could be trouble. Now, to make it shorter, I could convert it to hexadecimal and then write my own mathematical functions.

But, to make it even shorter, technically I could, break it up into base 256, based off of 256 available ASCII values (using an array of characters, one for each "digit").

So, that long number above would merely be:
char base256[7] = {chr(255), chr(0), chr(0), chr(0), chr(0), chr(0), chr(0)};

And thus, multiplication between 7 digits should take a lot less time than multiplication of 18 digits. This is my thought-process going into this situation, but I've never really worked with my "own" algorithms for numbers of base 256, so I'm just wondering if there's something inherently wrong with going about it this way?

I think our TI series calculators.. handle (large) numbers by using a logrithm to exponentally get a result.

For example:

2,456,456,987,123 + 100,345,457,164,221

Store the numbers into variables for easier reading:

store 2,456,456,987,123 -> A
store 100,345,457,164,221 -> B

Apply logrithmic properties:

LN A + LN B => (about 29 + 32'ish)
or LN (A*B)

so you are dealing with much smaller numbers at this point :)
(manipulation at this level should be much easier/faster)




to get your final answer, just perform an anti-log

e^(28.5397) + e^(32.2396) = 1.02802 x 10^(14) = 102,801,914,151,344


I think this is pretty close to how our professor explained it.. Hope this offers a different and perhaps some sort of useful perspective to your problemo. :)

Quote:

---

Originally Posted by Epo

And thus, multiplication between 7 digits should take a lot less time than multiplication of 18 digits. This is my thought-process going into this situation, but I've never really worked with my "own" algorithms for numbers of base 256, so I'm just wondering if there's something inherently wrong with going about it this way?

---

No, it should work. If you want it even faster, use base-65536 or base-2^32 if your processor supports 64-bit integer.

Hmm, thanks for the pointers. Now, if I combine BOTH! That...would probably be beyond me :)

But, given two ridiculously large numbers (I.e. 99999999999999999999999999999999)....wow, LN of that is just 73 (and some change). K, but I said ridiculous, so, let's assume a number with one million digits, even LN would still be fairly large I'd hope, then conversion to base 65536 (am I correct this is a short?), would then yield something even smaller.

All that's left to do is write conversion algorithms, and then functions to display the data without ruining a computer. Sounds good enough to me :)

That's very funny that you mention this. I happen to have just been discussing the same thing. See this link.

Getting into the brute work of this project, I'm just curious...

LN will definitely reduce the size of the number I'm working with by a very large factor, but, like most people know, LN, is just LOG with base "e" (2.something).

Is there a specific reason you picked to LN the number? Because LOG base 10 would further reduce a million digit number to the range of 1000000-10000000 (smaller than what LN would reduce to). Now, of course, LN Base one million would further reduce this, but that would be slightly impractical.

I'm just curious why you suggested (perhaps if there's a specific reason that TI uses LN) the LN function as opposed to the LOG with a larger base? Simply for the reason of making a choice or some deeper meaning?

You might use natural log essentially because you don't carry around an extra multiplicative factor for all of your computations (although, there is no reason why doing that would not work). Here is a link with the relevant info: http://mathworld.wolfram.com/NaturalLogarithm.html
Notice the extra factor you have when dealing with derivatives and integrals of/relating to logarithms to another base.

Quote:

---

Originally Posted by Epo

Is there a specific reason you picked to LN the number?

---

Tradition perhaps... and note that when calculating a number's logarithm you lose precision. So with log base 1000000 your results would be very unacurate.

Awesome, thanks for that link and the tips.

I figure I'm just going to stick with natural log mixed with some of my own conversion methods. What exactly those'll be, well....I guess we'll just have to wait and see :)
(Mainly because I don't know what they are yet)

Out of curiosity, Epo, how do you plan on performing a log (or ln) of an extremely long number?

That would be the tricky part wouldn't it ;) To use LN, the number has to be representable, but if it's representable, then it's small enough that we don't really need LN (Is what I'm expecting)

My plan so far:
Store the number in an array of characters to start;

Then, have a series of "possible" conversions, based on the size of the numbers being worked with, consisting of:

1 - Decimal Place conversion that'll make the numbers more relative
2 - Convert to base 65536.
4 - LN it. (will most likely lose out to...)
8 - Apply Epo's personalized LN that actually works with arrays of shorts. (I'm assuming this could be a little tough to code :) An extensive chat with my Calc prof is looming on the horizon)

And perhaps some more. The number beside each method gets added on to a running total, which will keep track of which conversions have taken place (and thus far, they're ranked in the order of importance I feel is right...I.e. never LN BEFORE Decimal Point conversions, but LN without the initial conversion is still okay). So if the running total = 5, I know a Decimal Point and Traditional LN conversion has taken place, so I know how to backtrack.

Alot of this is still up in the air, I'm juggling my CS weekly assignments with my Winsock Server with my full-on 3D "project", and now with this. This one is more of just a curiosity though, so it often ends up at the back of the list of things to do.

I don't know if my own LN function will be out of my reach, can't say I've ever tried anything like this before. I'm expecting that if I can get the LN (oh, and also reverse-conversion back to the actual raw number) down, then many other conversions won't be necessary. (The only reason I plan to convert to base 65536 to begin with is that it should reduce the number of elements in the array that I'll have to apply the LN to).

So, to answer your question, I still don't know. It's all up in the air and is something that I'm counting on being able to tackle when I get there. Perhaps I'm in over my head. Perhaps people do this everyday. I've no idea what to expect :) But I guess we'll see.