I Will Get That Job At Google. | Writing BigInteger better than JDK one
This morning I woke up and decided to get some practice with re-writing JDK classes and various algorithms. Yesterday I practiced with Fibonacci calculation in O(log(N)) so today I chose to write BigInteger from scratch. Here's a log from my evernote, you may find it interesting.
Interface
- Initialization
- Add
- Subtract
- Equals
- compareTo
Design
Each digit can be coded with 4 bits. So 1 byte theoretically may store 2 digits. But for simplicity we will store just 1 byte per digit, so field will looke like this: byte[] digits;
I think the easiest way to store BigInteger is less-digit-right. It means that it's easier to store 2456 as 6,5,4,2 in memory (because of extra overflows while adding etc).
Afaik BigInteger instances in Java are immutable so we may create additional instances. Main problem in operations is to determine size of new byte array for the result. Let's think what max value can occur:
Read full article from I Will Get That Job At Google. | Writing BigInteger better than JDK one
No comments:
Post a Comment