2

I think this question has more mathematical background than computional, then I'm gonna ask it here.

I was thinking about large numbers calculation. Let's say I have the number $16777735$ stored in memory like this:

$256^0$ $256^1$ $256^2$ $256^3$ $256^4$ $256^5$
--$7$----$2$------$0$----$1$-----$0$-----$0$--

How can I write this number to screen, let's say, in base $10$? Imagine that I CANNOT sum all the parts like $7 + 256\cdot2 + 256^3$, like I couldn't deal with a byte of this size. (I'm only interested in the algorithm, so imagine I have a really large number that can't fit in to a byte, this is just an example)

And also, how to calculate, like, lots of digits of $\pi$, with this same method? I need a way to do these calculations. I'm interested in learning, so I'm asking about the mathematical process of this.

Thank you :)

PPP
  • 2,041
  • just a note: --7--2--0--1--0--0-- is 16777735 in base 256. – udiboy1209 Jul 25 '13 at 07:39
  • 1
    There are many good books with algorithm for base conversion, e.g. Knuth's Seminumerical algorithms or Brent/Zimmermann's Modern Computer Arithmetik http://maths.anu.edu.au/~brent/pd/mca-cup-0.5.9.pdf

    @udiboy: you mean base 10

     – gammatester Jul 25 '13 at 08:11
  • 1
    Another very good book is Modern Computer Algebra by Joachim von zur Gathen. It goes however well beyond number representations. – siddhadev Jul 25 '13 at 08:21
  • I do not think that the calculation of irrational numbers to more digits than the compter can store will work in general. For example, $\pi$ has been calculated to awfully many digits, but that does not mean that we can do the calculation using only a small amount of memory. If you can work in integers or rationals, often tricks are available to save much memory. – Peter Feb 09 '17 at 19:04

1 Answers1

1

One method is to use the fairly standard method of converting to decimal, such as repeated remainders, eg you make up an array, and repeatedly divide the number by 10 (with carries), and carry the last digit over to the array.

For example, you divide 7.2.0.1 by 10, to get 205.153.25 r 5. You put 5 into a(0), and then go back for another digit, getting 97.142.2 remainder 3, the 3 is parked into a(1).

Another method that one could do, is to actually get your computer to work in decimal, like REXX does. There are papers by Mike Colishaw (who wrote REXX), about implementing decimal calculations in computer-arithmetic.

wendy.krieger
  • 6,856