Sunday, 26 September 2021

the cheapest science

Four of the more 'interesting' parts of the algorithm are shown circled below. Interesting in the sense of implementation using 1970s TTL chips.


First is the multiplication of a six bit (green) by a ten bit (blue) number, the result being - for our purposes - a 14 bit number (brown). In general of course, the product of a six bit and a ten bit number could be 16 bits (i.e. 1111111111 × 111111 = 1111101111000001), but it turns out that the maximum value that d ever attains (at least when calculating 263 digits of π) is 16371, a 14 bit number (i.e. 11111111110011). Specifically, this maximal value occurs when the product 17 × 963 (10001 = d) × (1111000011 = b) is computed. Importantly, the size of d, when appearing as the multiplicand, is six bits maximum; hence a six bit by ten bit multiplier is sufficient.

Second is the multiplication of an eleven bit number by the decimal value ten (i.e. 1010); an eleven bit by four bit multiplier is needed. The fact that the multiplying factor is constant (ten) rather than an arbitrary 4 bit number, suggests the possibility of some significant simplifications to the circuitry.

Third we have the division of a fifteen bit number (d has now become red), by an eleven bit divisor (g); both quotient and remainder are required. Of all the 'interesting' bits, this sounds the most alarming.

Fourth and finally we have the division of a six bit number (d is now green) by the decimal value ten (i.e. 1010); both quotient and remainder are required.  Both of these quantities are representable by 4 bit values (i.e. kpi and e). The number kpi is either an actual (decimal) digit of π, or ten (and so needs 4 bits maximum).



No comments:

Post a Comment