Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[kytuzian]

So I've been working on making my own programming language, for fun, and one of the issues I've had is that the arbitrary precision arithmetic I've implemented is really slow.

Of course, right now, all I have is the most basic method (except for repeatedly adding one) for doing addition, like you're taught in first grade. Normally its not much of an issue but I recently did 2 ^ 500000 for stress testing and it too 9 hours and 57 minutes, which is kind of unacceptably slow.

For multiplication I just have a system that repeatedly adds numbers together, because when I tried the standard grade school method it was actually significantly slower. For subtraction I have almost the same algorithm as for addition (although I am thinking about combining the two since they are pretty much the same). For division I have a long-division style algorithm in place. For exponentiation I simply do repeatedly multiplication.

However, a lot of the math is technically done with fractions in the language (so I don't have to program decimal math, and its more precise anyway), so I no longer even need the division operator.

Any help would be appreciated, and I'd be happy to show the source if anyone is interested.

[Killjoy]

Well. You can optimize additions as follows:
Perform additions by doing parallel additions of words. If you have two large binary number, split them into equal chunks that fit the largest register in your CPU. You might want to concatenate the smaller number to fit the larger.

Then, simply perform normal addition on these chunks. Then, simply go through each that overflowed, and add 1 to each 'next' chunk.

Multiplication, I really encourage you to implement binary long multiplication. It is actually quite a simple algorithm. Simply go though each bit in the first term, and if the bit is set shift the second term by the position, and add it to the result.

Once you have that down, you can implement Toom–Cook multiplication, which works by splitting the number, and essentially trading some multiplications for additional additions. Don't use the wiki source for this, it is way to general, and is bad at explaining what is actually happening.

If you don't care about all the bit twiddling, go an use the standard GNU BigNum library . It is written by people who actually know what they are doing, over the course of two decades, and is probably better than anything you can ever hope to write.

[kytuzian]

Well. You can optimize additions as follows:
Perform additions by doing parallel additions of words. If you have two large binary number, split them into equal chunks that fit the largest register in your CPU. You might want to concatenate the smaller number to fit the larger.

Then, simply perform normal addition on these chunks. Then, simply go through each that overflowed, and add 1 to each 'next' chunk.

Multiplication, I really encourage you to implement binary long multiplication. It is actually quite a simple algorithm. Simply go though each bit in the first term, and if the bit is set shift the second term by the position, and add it to the result.

Once you have that down, you can implement Toom–Cook multiplication, which works by splitting the number, and essentially trading some multiplications for additional additions. Don't use the wiki source for this, it is way to general, and is bad at explaining what is actually happening.

If you don't care about all the bit twiddling, go an use the standard GNU BigNum library . It is written by people who actually know what they are doing, over the course of two decades, and is probably better than anything you can ever hope to write.

Thanks for the response, I'll try some of your suggestions. I had considered the idea of using built-in types for addition. Also, the idea is for me to learn, so using a BigNum library kind of defeats that purpose.