Representing Whole Numbers

BH: Keep... But with my original wording in TIF A.

MF: lightly clean up to make the text more concise; do we really need to teach width and word??

On this page, you'll learn how computers store nonnegative integers.

As you know, numbers show up everywhere in computer algorithms—even if numbers aren't the topic. For example, the user may be interested in a picture, but that picture is an abstraction over numbers. Numbers are also used to find a specific item in a list. Over the next several pages, you'll look more closely at numbers inside the computer.

  1. They have now built factorial in 2.4.1, so this page should either give them a project with ONLY big nums and ask them to import ! or it should ask them to open their U2 Math project and then download and import bignums. --MF, 6/13/19
    If you look at the code, you'll see that it's a recursive reporter. How does it work? You first saw recursion on Unit 3 Lab 1 Page 2: Fractal Art.
    The factorial of a positive integer n (written "n!") is the product of all the integers from 1 to n. For example:
    Mary, you reduced this katex with a style tag (not proper CSS) because you couldn't figure out how to make it work with CSS. Fix this later. --MF, 12/6/17

    5! = 1 \times 2 \times 3 \times 4 \times 5 = 120

    Project file needs updated Unit and Lab numbers. -MF
    Click here to load this file. Then save it to your Snap! account. Try out these inputs:
    You might see different results depending on your computer's processor.
    1. (5)! reporting 120
    2. (10)! reporting 3628800
    3. (20)! reporting 2432902008176640000
    4. (30)! reporting 2.6525285981219103e+32
      5. This yellowbox had been a stray single line of white text after the FYTD and before the next heading. I think this is better. --MF, 5/31/20
      The "e+" means "times ten to the power of" so this notation means 2.6525285981219103 × 1032 = 265,252,859,812,191,030,000,000,000,000,000.

Fixed Width Computer Hardware

width: the number of bits that a CPU processes at a time

word: a binary sequence of that many bits

So why did Snap! display 20! in ordinary whole number representation but 30! in scientific notation? Every computer model is designed with a certain width, the number of bits that the processor reads from memory or writes into memory at a time. That number of bits is called a word. As of 2016, most new computers are 64 bits wide. The first microcomputer, sold in 1971, was four bits wide!

If you got an answer in scientific notation for 20!, you're using a 32-bit computer.
DAT-1.B.1

A 64-bit word represents 264 different values. We use half for negative numbers, one for zero, and the rest for positives. Half of 264 (which is 263 = 9,223,372,036,854,775,808) is about 9 × 1018. That means that the 19 digits of 20! just barely fit in a 64-bit word. But the 33 digits of 30! don't. So the computer hardware reports an overflow error, and Snap! computes an approximation.

Are processor widths always powers of two?
Processor widths don't have to be a power of two. Some old computers—the kind you see in old movies that filled a large room—used 12-bit, 36-bit, and 60-bit words. But modern personal computers started at 8 bits and the widths have been doubling with each new generation.
  1. Experiment in Snap!. What's the first integer whose factorial doesn't fit in a word?

Bignums

A multiple-word integer is called a bignum.
DAT-1.B.2

Why can't programming languages just use more than one word to represent an integer? They can. It's just that a single machine language instruction can only add one-word numbers. A programming language must work a little harder to make addition work with multiple-word values. Not all languages do this, but the highest-level languages do.

Tough Stuff
  1. A great example of a high-level programming language is Scheme. You can learn it from the free, online book Structure and Interpretation of Computer Programs.
The design of a programming language isn't just a question of taste; it can be a matter of life and death. Between 1985 and 1987, a therapeutic X-ray machine killed four patients and seriously injured two more because of several bugs in its software; one of the bugs was that a counter that was kept in an eight-bit-wide variable would reach its maximum value of 127 and then overflow to zero instead of 128. When the variable was zero, an important safety check was not performed. This would not have happened if the software had been written in a better programming language.
    You can use bignums in any Snap! project by importing the "Bignums, exact rationals, complex #s" library.

    You learned to import libraries on the Libraries page.

    They did not. --MF, 6/13/19
  1. Click on this block in the scripting area:
    USE BIGNUMS (true)
  2. Now try 30! again.
    30! reporting 265252859812191058636308480000000
    This (exactly correct) value is different from the (rounded off) floating point value above. (More about floating point in a moment.)
  3. Try 200!. The reported result won't fit on your screen, but you can see it this way:
    1. Hold down the control key and click the () ! block.
    2. In the menu that appears, choose "result pic."
    3. An image will download onto your computer or open in a new tab. You should be able to zoom in on it to read the digits.
    Please remind me again why this is worth doing. It feels clunky after a whole page of super abstract and ungrounded (i.e., "I can forget this as soon as the test is over") stuff that I only need to learn "because the teacher said so." --MF, 5/31/20
    It's much less clunky now. And the point is to demonstrate that there's no good excuse for any programming language to give approximate results to integer computations. -bh
  4. How many digits are there in 200!? (Don't count by hand; you have a computer.)