I started Project Euler over the Summer and totally forgot about it. The other day I started playing around with ideas of writing a library for integer math with arbitrarily-large numbers in C. As I started writing code, I remember a Project Euler problem (number 13) involving the sum of 100 50-digit numbers that I wanted to solve, so I got some basic arithmetic operations coded and solved it (woohoo, source is now on my Project Euler page).
Anyway, the point of this post is that I wanted to share the code with you. It’s now available here (download link) (moved to http://big-integers.googlecode.com) or on my Projects page. It’s very basic and doesn’t currently support division, comparison, or negative numbers. All of those things (and more!) are coming soon, but I just thought I’d post what I have done. I’ll probably keep updating it (and I’ll post to let you know) over the next week or so.
The algorithms for the three operations that it supports (addition, subtraction, multiplication) are all built off of the basic concepts that we all learned in elementary school. They’re all very simple (the multiplication looks a little confusing at first), and work exactly as if you were solving a problem on paper.
Enjoy!
PS. You can adjust the size (number of digits) of the bignum type in bn.h.
2 Comments for Working With Big Numbers in C
Logan Smith | December 11, 2009 at 5:45 am
Logan Smith | December 11, 2009 at 5:48 am
P.s. Your timestamp configuration is off, it’s not 5:45 in the morning anywhere in the US.
Also, I hate typing with large fingers and no buttons on the iPod touch keyboard.
I haven’t had time to mess with it yet (seriously, ha, I’ve done homework every night almost all day except today) but I plan on it this weekend/next week/Christmas break. In the meantime, I have a mathematical C programming challenge for you: find a simple way to take the decimal representation of a fraction and output the numerator and denomenator. I mean simple, like no loops searching for the denomenator or anything. I’ve been trying to do this in ti-basic at school since it’s fairly difficult to pull out a 17″ laptop and start programming without the teacher caring (except Stephenson). Also, I figure if I can do it easily on a calculator then it should be super easy on an actual computer. (plus the abundance of math functions available to ti-basic).
Also, check out my blag, I set up wordpress since I haven’t had time to make my own like I planned yet.