Programmer's Python Data  Bignum 
Written by Mike James  
Monday, 02 May 2022  
Page 3 of 3
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^{30} 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 32bit element with a digit in the range 0 and 1073741823, i.e. 0 to 2^{30}1. This may sound strange but it is exactly the same as using a hexadecimal representation with base 2^{4} with digits in the range 0 to 2^{4}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 32bit 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 32bit 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 16bit machine you can use base 2^{15} 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 32bit integer requires. In many cases, however, it is worth it in terms of simplicity. In chapter but not in this extract
The Number TowerOne of the problems any stronglytyped 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 dynamicallytyped 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 builtin integer type. Next we have Rational, which is the model for the rational type even though it isn’t a builtin type. Then comes Real, which is essentially the builtin float and finally Complex, which is the builtin 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 CrunchingIf 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
Programmer's Python


Last Updated ( Wednesday, 04 May 2022 ) 