Bignums anno 1864

[Niels Möller]

Hi,

I was looking up what wikipedia says about Karatsuba multiplikation, and
found a rather interesting reference to Charles Babbage,

https://archive.org/details/bub_gb_Fa1JAAAAMAAJ/page/125/mode/2up

  Since every calculating machine must be constructed for the
  calculation of a definite number of figures, the first datum must be
  to fix upon that number. In order to be somewhat in advance of the
  greatest number that may ever be required, I chose fifty places of
  figures for the Analytical Engine. The intention being that in such a
  machine two numbers, each of fifty places of figures, might be
  multiplied together and the resultant product of one hundred figures
  might then be divided by another number of fifty places. It seems to
  me probably that a long period must elapse before the demands of
  science will exceed this limit.

50 digits corresponds to roughly 166 digits, so he went for much higher
precision than present-day 64-bit floating point. And then we get to
bignums, where he describes how to do multiprecision operations, e.g,
multiply of 100-digit numbers using four 50-digit multiply operations,
and concludes:

  Thus it appears that whatever may be the number of digits the
  Analytical Engine is capable of holding, if it is required to make all
  the computations with $k$ times that number of digits, then it can be
  executed by the same engine, but in an amount of time equal to $k^2$
  times the former.

It seems estimated computation speed "Supposing the velocity of the
moving parts of the engine be not greater then forty feet per minute"
(0.2 m/s) was one second per addition, one minute per multiplication,
all operating on 50-digit values.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.