Full multiplication when you can only halve and double

When I was shown this math trick as a child, little did I know that it would come in handy in the future for creating an esoteric programming language!
Support me on Patreon: / timwi
Page on Esolangs wiki: esolangs.org/wiki/Funciton
Interpreter on GitHub: github.com/Timwi/Funciton
00:00 A long time ago...
00:20 The multiplication trick
01:43 What Funciton operations can do this?
03:08 Planning the algorithm
04:48 Writing it in Funciton
06:36 The (perennial) problem with negative numbers
07:45 Writing the fix for negative numbers
09:14 New syntax: private functions
09:57 Testing
10:24 Exploring an alternative fix for negative numbers
11:28 Comparing the performance of both
12:09 Exploring a third fix for negative numbers
12:49 Responding to a comment on the Increment function
13:31 Why the trick works: comparing it with long multiplication
16:08 Why the trick works: mathematical proof
18:03 My challenge to you

[@harinathrao1]

The video are great

[@pinecubes]

such a clear explanation and interesting problem :) im going to try to use this technique to implement multiplication on a redstone ALU

[@MrSquares]

Anyone else notice how he kind of looks like the Grinch? (Love the vids btw)

[@gerocastano8]

I would write the division as: a / b = (0, a), if a < b else let q, r = (a-b)/b return (q+1, r)

[@TimwiSoMuchCode]

Interesting! At first glance I think your idea would give the correct answers. However, if I’m not mistaken, it would be an exponential-time algorithm. In my next video, I show an algorithm that relies on shift-right, thus ensuring linear time complexity.

[@gerocastano8]

Why would it be exponential? The argument is always decreasing by at least 1 (we could separately implement division by zero errors and negative inputs), so it is at least linear time in the worst case. In general the time complexity would be O(a/b)

[@TimwiSoMuchCode]

@@gerocastano8 Yes, and O(a/b) is exponential time, because it’s in the ballpark of O(2ⁿ) where n is the number of bits in the input. My algorithm is linear time, that is O(n), where n is the number of bits in a. I did a brief summary of this in the subtraction video at this timestamp: kzbin.info/www/bejne/n3PQaaGgapaFopo

[@gerocastano8]

@@TimwiSoMuchCode oh, you’re accounting also for the number of bits. In that case, yes, my algorithm is exponential. I was just assuming that subtracting numbers was a constant operation.

[@TimwiTerby]

@@gerocastano8 Your algorithm is still exponential even with that assumption. You are subtracting a/b times, and a/b is exponential in the number of bits in a.