How Does Bignum Work?

You don’t have to know how Python’s amazing integer arithmetic works to make use of it, but it might help you understand why it is reasonably efficient. The underlying hardware that your program runs on has special hardware that performs arithmetic – the Arithmetic Logic Unit, ALU. This can take integers of a specified size and perform arithmetic usually one operation per clock pulse. This makes it very attractive to use integers that have a fixed size that will take advantage of the ALU to complete operations very quickly. This is fast and efficient, but it raises the issue of overflow during a computation – which is how programmers have always thought about machine arithmetic.

Python, however, decouples implementation from the integer abstraction and this is what any modern language should try to do. You might think that the best way to implement Bignum is to just keep adding bits as the number gets bigger, but this doesn’t make the best use of the hardware. A better method is to treat the basic arithmetic size of the machine as a single digit in a base 2³⁰ representation. The complete number is an array of these digits and it is this array that gets bigger or smaller as the number changes in value. For a small number the array has a single 32-bit element with a digit in the range 0 and 1073741823, i.e. 0 to 2³⁰-1.

This may sound strange but it is exactly the same as using a hexadecimal representation with base 2⁴ with digits in the range 0 to 2⁴-1. In this case each digit takes four bits and arithmetic can be performed four bits at a time. Now when you perform an addition of two numbers that are small enough to have just one digit, all you have to do is add the two 32-bit digits together - this can be done using the ALU and is as fast as standard binary because that's what it is. If there is a carry from adding the first two digits then another 32-bit digit is added to the result and the computation continues. In this way the Bignum can be processed one digit at a time using the ALU to do the arithmetic on each digit with good efficiency as the number gets bigger.

In practice, the size of the digit used can be adjusted to the size of the machine so on a 16-bit machine you can use base 2¹⁵ and still get the best performance for small values. Python typically preallocates small integers as constants in the range -5 to 256 ready to use without conversion. The only potential downside is that each integer is an object which contains an array of digits and this is at least 28 bytes in size, i.e. considerably larger than the 4 bytes a standard 32-bit integer requires. In many cases, however, it is worth it in terms of simplicity.

In chapter but not in this extract

• Rational
• Decimal

The Number Tower

One of the problems any strongly-typed language has to solve is how to organize the different types of numbers into an inheritance hierarchy so that we start from the simplest objects and progress to more complex objects. Most get it horribly wrong so that the hierarchy isn’t actually useful. For example, in C# the Numeric type, which is at the top of the hierarchy, doesn’t have a + operator defined so you can’t assume that all numbers can be added. Python on the other hand, even though it is a dynamically-typed language, does get it right.

Python defines a number of Abstract Base Classes (ABCs) which it refers to as the Number Tower to express the relationship between the different number types. At the top of the hierarchy is Integral, which is essentially the built-in integer type. Next we have Rational, which is the model for the rational type even though it isn’t a built-in type. Then comes Real, which is essentially the built-in float and finally Complex, which is the built-in complex type. Each of these are virtual classes which are designed to allow the implementation of numbers of the type specified. You can mostly ignore these classes unless you want to create a new numeric type somewhere between two of them. See Chapter 15 for more.

Number Crunching

If you need to crunch numbers there are a set of Python modules that are essential - but not necessarily for the average programmer. The least you need to know about Python numerics is provided here with some help from the documentation. If you need to do more with technical computations then take a look as SciPy which includes NumPy , the numerical calculation module and Pandas for data analysis. All excellent and to be recommended, but beyond the scope of this book.

Summary

• All languages have a set of basic data types which are usually designed to take advantage of the hardware’s abilities. The most common basic types are integers and floats – integers cannot have a fractional part and floats always have a fractional part.

• Python 3.0 doesn’t have a standard fixed size int type. Instead it supports a “bignum” integer type. Bignums are very special in that they use unlimited precision. As a calculation proceeds more digits are added to accommodate the result. The only limit is the amount of memory available.

• The standard arithmetic operators work with bignums and produce bignums with the exception of division which produces a float.

• You can also do bit manipulation with bignums and this too is with unlimited precision. This is not something most programmers are used to.

• The bignum implementation is clever and efficient and its additional costs are well worth it to avoid the problems of overflow.

• The rational number type also provides precise representation, but of fractional values.

• The decimal number type uses a decimal representation to avoid the unexpected behavior of even high-precision binary arithmetic. Decimal numbers are manipulated in exactly the way that you would do the calculation using paper and pencil and hence comply with what a human expects.

• The number tower is a set of virtual classes designed to make the relationships between the different types of number clear.

• There are Python modules that take you beyond the basics and these, especially SciPy, NumPy and Pandas, are worth finding out about.

Programmer's Python
Everything is Data

Is now available as a print book: Amazon

Contents

1. Python – A Lightning Tour
2. The Basic Data Type – Numbers
      Extract: Bignum
   
3. Truthy & Falsey
4. Dates & Times
5. Sequences, Lists & Tuples
      Extract Sequences 
6. Strings
      Extract Unicode Strings
7. Regular Expressions
8. The Dictionary
      Extract The Dictionary 
9. Iterables, Sets & Generators
      Extract  Iterables 
10. Comprehensions
       Extract  Comprehensions 
11. Data Structures & Collections
12. Bits & Bit Manipulation
         Extract Bits and BigNum ***NEW!!!
13. Bytes
        Extract Bytes And Strings
        Extract Byte Manipulation 
14. Binary Files
15. Text Files
16. Creating Custom Data Classes
        Extract A Custom Data Class 
17. Python and Native Code
        Extract   Native Code
    Appendix I Python in Visual Studio Code
    Appendix II C Programming Using Visual Studio Code

<ASIN:1871962765>

<ASIN:1871962749>

<ASIN:1871962595>

<ASIN:187196265X>

Related Articles

Creating The Python UI With Tkinter

Creating The Python UI With Tkinter - The Canvas Widget

The Python Dictionary

Arrays in Python

Advanced Python Arrays - Introducing NumPy