skew binary & suan-pan

Date view Thread view Subject view Author view

From: Dave Long (
Date: Mon Jun 26 2000 - 11:23:23 PDT

In part of Chris Okasaki's thesis, he mentions "skew binary"
encoding, where the occasional use of a '2' digit alongside
'0' and '1' allows amortized carry propagation.

The suan-pan (chinese abacus) differs from the soroban (the
japanese version) in having 5 ones beads and 2 fives beads,
instead of just 4 ones beads and 1 fives bead.

Is it possible the extra beads serve an equivalent purpose
to the '2' in skew binary? Given that pattern recognition
is cheap relative to bead movement on an abacus, I'd guess
that a fancier technique which avoided log n manipulations
may have been preferable.

(In which case, though, why would the soroban lack the extra
beads? Perhaps they were used when computations were easier
to carry out in bases other than decimal?)


Date view Thread view Subject view Author view

This archive was generated by hypermail 2b29 : Mon Jun 26 2000 - 11:12:36 PDT