Why use a higher base to implement BigInt?

Question

I am trying to implement BigInt and have read some topics and articles regarding this, most of them suggested using higher bases (256 or 2 ^ 32 or even 2 ^ 64).

Why are higher bases suitable for this purpose?

Another question is how should I convert the string to a higher base (> 16). I read that there is no standard way other than base64. And the last question, how can I use these higher bases. Some examples would be great.

Answer 1

CPU cycles spent on multiplying or adding a number that fits into a register tend to be identical. This way you get the least iteration and the best performance using the whole register. That is, in a 32-bit architecture, make your base block 32 bits, and in a 64-bit architecture, make it 64 bits. Otherwise - say, if you fill in only 8 bits of your 32-bit register - you waste cycles.

Answer 2

• the first answer stated it in the best way. I personally use the base 2 ^ 16, so as not to overflow when multiplying. This allows every two digits to be multiplied by each other once without overflow.

• Converting to a higher base requires a fast division method, as well as packing numbers as much as possible (assuming ur BigInt lib can handle multiple databases).

Consider base 10 → base 2. Actual conversions will be 10 → 10000 → 32768 → 2. This may seem slower, but converting from base 10 to 10000 is very fast. The number of iterations to convert between 10000 and 32768 is very fast, since there are very few digits to iterate over. Unpacking 32768 to 2 is also very fast.

So, first pack the base on the largest base that it can go to. To do this, simply connect the numbers together. This base should be <= 2 ^ 16 to prevent overflow.

Then combine the numbers together until they become> = the target base. From here, divide the target base using the fast division algorithm, which usually overflows in any other scenario.

Quick code

if (!packed) pack() from = remake() //moves all of the digits on the current BigInt to a new one, O(1) loop addNode() loop remainder = 0 remainder = remainder*fromBase + from.digit enter code here`exitwhen remainder >= toBase set from = from.prev exitwhen from.head if (from.head) node.digit = remainder else node.digit = from.fastdiv(fromBase, toBase, remainder) exitwhen from.head 

Look at fast division

 loop digit = remainder/divide remainder = remainder%divide //gather digits to divide again loop this = prev if (head) return remainder remainder = remainder*base + digit exitwhen remainder >= divide digit = 0 return remainder 

Finally, unzip if you need to unzip

The packaging simply combines the numbers together.

Base Example 10 to Base 10000

 4th*10 + 3rd *10 + 2nd *10 + 1st 

3. ???

You should have a Base class that stores the alphabet + size for toString. If the base is not valid, then simply display the numbers in a comma-separated list.

All your methods should use the base BigInt base, not some constant.

What all?

From there you can do something like

 BigInt i = BigInt.convertString("1234567", Base["0123456789"]) 

Where [] is overloaded and will either create a new database or return an already created database.

You can also do things like

 i.toString() i.base = Base["0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"] i.base = 256 i.base = 45000 

etc. ^ _ ^.

Also, if you use integers and want to return the remainders of BigInt, the separation may get a bit confusing = P, but still pretty easy ^ _ ^.

This is the BigInt library that I encoded in vjass (yes, for Warcraft 3, lol, don't judge me)

Things like TriggerEvaluate(evalBase) are just so that the threads don't get stuck (the limit of an evil operation).

Good luck: D