In an effort to fight off atrophy from using AI too much, I’ve started playing with slide rules - basically, calculators before calculators (after abacuses). They are quite hard to buy in this day and age, but there are some paper ones you can print out. And if you are good at PCBs maybe you can help me try to make one?

The way slide rules work is: if you mark a ruler with logarithmic spacing, multiplication becomes addition. This is a pretty cool maths trick in that you are adding exponents, and then you can pow() them back to reality. I think of it as “working in Log10 space” which would probably make an actual mathemagician cringe. But basically, you slide one scale along another, read off the answer, and keep track of the decimal point in your head. It’s absolutely amazing engineers built bridges and got to the moon with this.

Meanwhile, nearly everything in machine learning is a matrix multiplication. Which, as you can imagine, is mostly multiplication. So I had a thought: what if you convert a matrix into log10 space once, do all the “multiplies” as integer additions, and convert back at the end? Remove multiplication altogether, like the slide rule does. I got right on that with thinking.

Ah, I C

The digital version of a slide rule scale is a lookup table. I used 10,000 ticks per decade, so tick 4969 sits at $10^{0.4969}$, which reads as 3.14. As with a slide rule, a number becomes a “cursor” position. It stores a tick, the decade, and the sign. The decade and sign need to be kept around because of the way you use a slide rule - you can have a look if you’re interested (you need to do some mental bookkeeping with a physical slide rule, it’s not as straight forward as a digital calculator).

While doing this I learned that IEEE doubles are already half a slide rule. The exponent field of a double is floor(log2), and the mantissa bits (the numbers after the dot for the uninitiated) interpolate between powers of two. So converting a number to its cursor takes a couple of bit shifts and two small table lookups. No logarithm gets computed at runtime, and no normalisation either, since the tables are indexed straight off the bits.

Multiplication is then just this:

// A position on the rule: which tick, which decade, and the sign
typedef struct { int16_t tick; int16_t decade; uint8_t neg; } cursor;

// Multiplication is addition of positions, with a decade carry
static inline cursor slide_multiply(cursor a, cursor b) {
    int t = a.tick + b.tick, d = a.decade + b.decade;
    if (t >= M) { t -= M; d++; }
    cursor r = { (int16_t)t, (int16_t)d, (uint8_t)(a.neg ^ b.neg) };
    return r;
}

An integer add, a compare, and an XOR. No floating point multiplier anywhere. It seemed to me like this should be super fast.

Eh, Not So Much

I made a little 8x8 matmul benchmark to test against the plain naïve triple loop:

pair 1: naive   0.7210 μs (  1.42 GFLOP/s)  |  slide  17.7919 μs (  0.06 GFLOP/s)

Twenty five times slower. I hadn’t optimised anything other than the multiply though. I was calling pow() to reapply the decade on every single element in the matrix multiply. That was converting each matrix entry to a cursor eight times instead of just once. I also wasn’t doing any compiler optimisations (-O2 for example). So I updated those to see if it would help, and the slide version got 26x faster. The funny part was the naïve version also got 10x faster, because the optimiser (being the helpful thing it is) turned those operations into vectorised multiply-adds:

pair 2: naive   0.0670 μs ( 15.28 GFLOP/s)  |  pre   0.6941 μs (  1.48 GFLOP/s)

So the slide rule way was still 10x behind. Every “multiply” in my version is just a cheap integer add, followed by two table lookups (O(1)ish) to get back to linear space and then an accumulate. The lookups are seemingly what wound up biting me.

Maybe bigger matrices?

My last test was scale. There are some actual mathematical techniques to improve matrix multiplication, but they generally only apply with large matrices. I thought maybe this might be the same. Maybe it can only help when you move to much larger matrices where maybe caching hurts multiplying a long row of numbers. So I tried a 1024 matrix and I turned off the vectoriser to keep SIMD out:

n = 1024 (each matrix 8.0 MB)
  naive ijk    2.11 GFLOP/s
  naive ikj    7.70 GFLOP/s
  slide ijk    1.13 GFLOP/s
  slide ikj    1.77 GFLOP/s

The gap narrowed from 10x to about 2x in the “cache hostile” loop. So I was kind of half right. When the hardware multiplier is starved, its advantage mostly evaporates.

But the slide rule technique never seems to out performs the naïve approach. Which make sense since the slide version walks the same columns and eats the same cache misses, then adds its own table lookups on top - maybe if this was somehow baked into the chip? The thing I hoped would sink the naïve version really just sinks both. Reordering the loops to stream rows instead of columns (ikj above) fixed the cache problem for free and put the naïve version 4x ahead again.

After reading about this a bit more, and asking Mr. Claude, I was probably doomed from the start as “A modern FPU retires multiple multiplies per cycle, while a table lookup costs several cycles and extra memory traffic.” Which makes sense, but I learned running through this quick experiment - no ragrets :).

📝 Side note: you also, obviously, lose precisions. Each product carries about $2x10^{-4}$ of tick rounding error, and a dot product of 1024 terms compounds that to roughly two reliable digits. A slide rule’s 3-4 significant figures do not survive big matrices. I was thinking for some machine learning workloads that might not matter… similar to quantization.

I still think the old trick deserves a rematch somewhere multiplication is genuinely expensive, like a multiplier-less microcontroller or a small FPGA or something.

Maybe a follow-up experiment is in order :D.