Arbitrary-Precision ArithmeticDate: 08/08/2003 at 19:30:48 From: Kurt Subject: Multiplying beyond floating point calculations The programming language I use (QBasic V4.5) can display all digits of numbers up to 10^15. Suppose I wanted to multiply numbers that are greater than 10^15, say 8641578146853213165*998574385979598791785978. How could I use the programming language's math to compute that larger number in the quickest way, and yet display every single digit in the product? The problem I would have is checking my answer, because I don't know of many ways I could actually multiply numbers that big. I thought maybe I could divide each number into separate groups of seven digits because 9999999*9999999 would be the biggest possible multiplication of seven digits and it is small enough to work. Then maybe I could multiply each group of seven by all the other groups of sevens the way you do one digit at a time in pencil and paper multiplication. Would this work? Is there a faster or easier method? I just like to try difficult things like this for the fun of it. Thanks so much. Date: 08/09/2003 at 22:26:28 From: Doctor Warren Subject: Re: Multiplying beyond floating point calculations Hi Kurt, Thanks for writing to Dr. Math. What you're looking to do is called "arbitrary-precision arithmetic." Using arbitrary-precision arithmetic, you can store and operate on numbers as big as your computer's RAM, or, if you're really clever, as big as your computer's RAM and hard disk space combined! The simplest conceivable arbitrary-precision system would use an array of bytes, and have each byte store one decimal digit. To perform arithmetic on these arrays of digits, you would just perform the normal grade-school algorithms, adding digit-by-digit and keeping track of the carries, subtracting digit-by-digit and keeping track of the borrows, and so on. This is a very naive approach, however, because it's obviously not very efficient to use an entire byte to store a single decimal digit. However, I recommend you start with this kind of program, because it's very easy to debug, and you'll get the hang of the methods involved. When you're ready, you can step up to more efficient approaches. Arbitrary-precision arithmetic is nothing new. There are in fact many many libraries on the Web that you can use in your programs. Some programming languages (like Lisp and Java but not QBasic, I suppose) even have arbitrary-precision functions built into them. Here's a page full of arbitrary-precision libraries: List of Arbitrary Precision C packages - Mark Riordan http://www.csc.fi/math_topics/Mail/FAQ/msg00015.html It's not terribly up-to-date, but that's okay. The one I've used personally is called "BigNum." You can get a copy of it from: /afs/athena.mit.edu/contrib/bignum http://www.mit.edu/afs/athena.mit.edu/contrib/bignum/ It's in C though, so you might need to learn some things before you can fully understand it. These libraries are also very much optimized for the kind of operations done in cryptography (the technique of encoding messages so that they can't be read by anyone but the intended recipient), like exponentiation modulo some integer. And just to make it easy for you to check your BIG results, here's a calculator (written in Java) that runs in your Web browser. Arbitrary-precision Integer Calculators http://www.cis.ksu.edu/~howell/calculator/calc.html Let me know if you have any more questions. - Doctor Warren, The Math Forum http://mathforum.org/dr.math/ Date: 08/12/2003 at 23:18:34 From: Kurt Bachtold Subject: Arbitrary precision division How do you calculate one number divided by another number if the numbers are larger than what is allowed on the computer? In QBasic, the programming language I use, I can divide any two numbers up to fifteen digits long. But suppose I want to divide a by b and a is 60 digits long, while b is 30 digits long. I figured I could divide each number into groups of 15 digits as follows: a = jjjjjjjjjjjjjjjkkkkkkkkkkkkkkklllllllllllllllmmmmmmmmmmmmmmm b = xxxxxxxxxxxxxxxyyyyyyyyyyyyyyy The next step (I think) is to divide each fifteen-digit part in a by each fifteen-digit part in b and do something with the results, but I do not know what that something is. Please tell me how to go about doing this so I can continue my project on arbitrary precision math. Thanks! P.S. I just want to tell you that I love browsing through the questions and I am glad that you take the time to answer mine. I don't know what I would do without your help :). Date: 08/13/2003 at 00:17:08 From: Doctor Warren Subject: Re: Arbitrary precision division Hi again Kurt, I responded to your last question about how to do arbitrary-precision arithmetic and I hope my reply helped you get started. Did you choose to represent your arbitrary-precision numbers as arrays of decimal digits as I suggested? Performing division on arrays of decimal digits is very easy - it's just grade-school long division, just as you remember doing in elementary school. The reason this algorithm is useful to schoolchildren is that it breaks down a very large number into small pieces, each of which can be handled mentally. Your computer is going to have to do the same thing - it's going to have to break down a division of a really big number into pieces that can individually fit into its processor. When you store your numbers as an array of decimal digits, you are quite obviously working in decimal, base ten. You can also do long division in a different base, and the rules don't change at all. For example, here's a long division problem in hexadecimal: 1149 ------- 76 | 7F812 76 -- 98 76 -- 221 1D8 --- 492 426 --- 6C Do this long division on your own if you need to prove to yourself it works exactly the same as it does in decimal. You're going to program your computer to do the exact same things that you do when you do the division by hand - testing for the largest multiple of the divisor (up to N-1), subtracting, and bringing down the next digit. Now, here's the trick that will make this seem easy: there's no limit to the arithmetic base we can use. In hexadecimal, each digit is represented by exactly four bits. If you chose to implement your arbitrary-precision system with four bit units, it would be rather awkward, however - so how about a bigger base? Your computer is very capable of dealing with 8-bit quantities (bytes). An 8-bit number can range from 0 to 255. If you work with 8-bit quantities, you're effectively working in base 256. If you store your arbitrary-precision numbers as arrays of 8-bit numbers, you're essentially representing them as strings of base-256 digits. Here's an example: bytes: 00100101 11010001 01010101 digits: (37) (209) (85) place values: 256^2 256^1 256^0 This three-byte number is composed of three base-256 "digits." To figure out what the whole number means, just as in any other base, you multiply each digit by the value of its place. The digit (37) is in the 256^2 place. The total number is 37*256^2 + 209*256 + 85, or 2,478,421. Now, as I said, there's no limit to what base you can do your arithmetic in. You can do long division on base-256 numbers exactly the same way as you do it on base-10 numbers. So here's the algorithm written up in pseudocode: DIVIDE(a by b) { LET current_segment = most signifcant digit of a; WHILE there are digits left in a LET accumulator = 0; LOOP WITH i FROM 0 TO N-1 LET previous_accumulator = accumulator; LET accumulator = accumulator + b; IF (accumulator > current_segment) { OUTPUT i; BREAK OUT OF LOOP; } END LOOP LET remainder = current_segment - previous_accumulator; LET current_segment = remainder followed by next digit of a; END WHILE END DIVIDE (Make sure that you completely understand this pseudocode algorithm before you begin to code it in real code. Test it out on a base-16 problem by hand!) Does this help? Feel free to ask more questions! - Doctor Warren, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/