flâneur

Labor of Division (Episode IV): Algorithm D

ridiculousfish.com · 2,566 words · saved by 1 readers

Algorithm D is Knuth's celebrated multiword integer division algorithm. This post tries to make Algorithm D approachable, and also has an idea for an improvement, in the last section. A followup post provides code to take advantage of that improvement. To build intuition, we'll use concrete base-10 values, instead of a general base and digit count like Knuth does. It should be straightforward to generalize to arbitrary bases and digit counts. The problem is dividing one big number by another big number. The numbers are big enough to require multiple "digits", where a digit is a number in some comfortable base. The examples will be base 10, but in practical applications the base is the width of a hardware divider, or sometimes half that. For example, when dividing a 256-bit number by a 128-bit number, we may pick 64-bit digits, for a base of 2 64 2 64 , which is huge. It's hard to beat grade-school long division. In long division, we crank out the quotient digits from left to right by

Labor of Division (Episode IV): Algorithm D recent posts | all posts | about fish Labor of Division (Episode IV): Algorithm D April 28th, 2021 Algorithm D is Knuth's celebrated multiword integer division algorithm. This post tries to make Algorithm D approachable, and also has an idea for an improvement, in the last section. A followup post provides code to take advantage of that improvement. To build intuition, we'll use concrete base-10 values, instead of a general base and digit count like Knuth does. It should be straightforward to generalize to arbitrary bases and digit counts. Background

saved by

related reading