4000 Years Old Multiplication Trick
HTML-код
- Опубликовано: 27 сен 2024
- A four thousand years old way of multiplying numbers that you've never seen before!
Support this channel: / inigoquilez
Support: / inigoquilez
Donate: www.paypal.com...
Subscribe: / inigoquilez
Follow: / iquilezles
Follow: / inigo.quilez
Music by Bent Stamnes ( / gloom303 )
Hi Inigo! I stumbled across your raymarching stuff a little while ago, and it helped me so much doing a university assignment recently. Your offhand "this can work in 4d too" in the deriving the SDF of a box video gave me the inspiration i needed to be able to write a 4D viewer for a project we had to do, and your SDF formulas and articles about it on your website were invaluable in helping me solve issues that came up. I obviously gave you a lot of credit in the written portion, but thank you so much for all the help =)
I came up with this formula at about fourteen years old in the early eighties, thinking about how close a x b would be to their average squared. This as a way to be able to do larger multiplications from the top of your head. My middle school math teacher then proved that my formula was correct.
Never used it for anything. Then about twenty years later I found out this formula was known and used to make old 8-bit CPUs do fast multiplications (as you can easily create tables for it). I had an 8-bit computer at the time and never thought of this.
And now, watching this video, I find out this formula is much older than that.
I clicked on this video from 3b1b's description. Then I started recognizing the voice, and sure enough, it was you!
you can make your table half as big by storing only even entries and adding floor(index / 2) to the value if the index was odd. floored division by two is just one bit shift to the right and checking whether the index was odd is the same as checking the carry flag. (i.e., compute the actual index by shifting the index one to the right then check carry flag and add the actual index to the lookup value if the carry flag was set)
Instead of floor(index/2) you can simply make the less significant bit a 0 and do the lookup
@@katech6020 that's right. Since every entry in the table is two bytes anyways, this is optimal.
3blue1brown posted contestant picks, so this will finally get more attention! It looked really interesting in his 20 choices.
Nifty as always. Wish you posted more often.
I hear you (and I wised too, I do what I can)
The Gameboy fun fact was awesome!
Very nice video, i love the computational usefulness ! To go further, this relation is called a polarization identity. It can be used to recover the symmetric bilinear form associated to a quadratic form. A famous application of the polarization identity is the parallelogram law : a relation between the sides of a parallelogram and its diagonals.
Great video! Really nice idea to use LegoBricks :-)
Thanks :)
I am amazed with all the finding you presented. Thanks for the video. :)
Delightful!
what an interesting opening and computer science knowledge
Great video about an equation I can't praise highly enough and found in geometrical form in Euclid's 'Elements' book 2 proposition 8. It is also the difference of two squares and the Pythagoras theorem in a slightly different guise. It is commonly referred to as the 'quarter squares rule' for the reasons you have explained and tables of quarter squares were present in Chambers Mathematical Tables. Great stuff.
as a person from Babylon, I am proud of it
APPARENTLY I NEEDED THIS
Amazing!
*4000 Years Old Multiplication Trick: The Babylonian Method and Its Applications*
* *0:00** Introduction:* The video introduces a historical multiplication method known as the Babylonian method, which does not rely on traditional multiplication tables.
* *0:10** Geometric Visualization:* The method is visually explained using squares and rectangles, demonstrating how the area of a larger square (a+b)² can be decomposed into the area of four rectangles (4ab) and a smaller square (a-b)².
* *1:16** The Babylonian Formula:* This leads to the algebraic formula: a*b = ((a+b)² - (a-b)²)/4
* *1:41** Historical Context:* The Babylonian method, estimated to be 3000-4000 years old, likely utilized lookup tables of squares to simplify calculations in their base-60 number system. [From VectrexForever's Comment] This method was also used to optimize multiplications in early 8-bit CPUs.
* *2:28** Optimizing with Quarter Squares:* Instead of storing full squares, the Babylonians could have used a table of quarter squares (n²/4) to eliminate the division by 4 in the formula. [From RajeshGanesan92's Comment] Using a quarter squares table, multiplication can be further simplified as a*b = (a+b)²/4 - (a-b)²/4, requiring only lookups and additions/subtractions.
* *3:21** Integer Results:* The video explains that despite the quarter squares sometimes having a 0.25 fractional part, the final multiplication result will always be an integer.
* *4:28** Generating the Table:* The sequence of quarter squares can be efficiently generated by observing the pattern of differences between consecutive entries, avoiding the need for direct multiplication.
* *5:48** Practical Application and Limitations:* The video creator experimented with using the Babylonian method for base-10 multiplication but found the lookup process to be slower than traditional memorized multiplication tables. [From dikkedorus's Comment] The creator also acknowledges that the method might not be practical in situations where memory for storing lookup tables is limited.
* *6:38** Use in Microprocessors:* The Babylonian method can be advantageous for microprocessors lacking hardware multiplication, like those found in the Game Boy, due to its reduced computational complexity.
* *7:35** Generalization to Real Numbers and Vectors:* The method extends beyond integers and can be applied to real numbers and even vector dot products. [From romaing.1510's and hermanchau5962's Comments] This generalization is known as the polarization identity.
I used gemini-1.5-pro-exp-0801 on rocketrecap dot com to summarize the transcript.
Cost (if I didn't use the free tier): $0.07
Input tokens: 16899
Output tokens: 569
I never heard of a lookup-based multiplication like that in practice. Is there any known use case? The only hardware I've written manual muls for didn't have that kind of storage, but it sounds like a good trade-off under certain circumstances.
I assume that the LUTs would be done in software.
Great video Imigo! I have a correction to your 8-bit multiply though. The babylonian method code you presented would break where b>a, you need an extra conditional to swap the operand order.
Lookup tables eh? They were demoscene coders at heart ;)
Blows my mind how this is 4000 years old.
I really believe that there was a pre-ice age civilization that was excellent in fishing, navigation, astronomy and math. But never bothered developing a modern empire.
All our time and navigation is still based on a base 60 system and it would be only straightforward to adjust everything else to base 60 if you were only interested in navigation and astronomy. The knowledge about our solar system encoded in the choice of this system should not be there if not created by a sophisticated naval navigator.
The technology was more advanced than we are today, the earth had about 6 advanced civilizations that were wiped off the map through natural disasters or war. we are the 7th. Every new technology you see today is trickled down to the masses as something new.
fascinating content as always, thanks for sharing!
That is very interesting.
I was recently writing library for working with big uints. So my first thought after watching this video was "Can I use Babylonian method ?", but then I realised that I would need lockup table much larger than maximum int.
Generating square on fly by adding 0+1+1+2+2+3+3+4+... probabaly also won't be effective.
So I will most probably stick with our classic method. But you insipired me to have other look at it.
You can combine. You can babylon-mult 2 bytes at a time, and have you table be just 128kb. But, for big-num, there are other methods anyways. And for really BIGnum don't we use the Fourier Transform?
I implemented big uint multiplication by representing each uint as a uint32[N] (which I think about in it's binary representation), and then multiplying specific pairs of uint32's together, which results in uint64's, that I then bitshift and add to the result. It's the fastest approach possible.
8 montsh have passed and I still don't understand how to use Fourier Transform.
But I don't use big numbers that oftern so it will be a problem for me.
Yes ofcourse!
Oh wow!
loved the soeed of the video
This technique was also used much earlier than 8 bit microprocessors in analog computation. It was called the quarter-square multiplication technique. I will put a link to a google book in a reply.
RUclips deletes the link so just find
Instrument Engineers' Handbook, Volume Two: Process Control and Optimization - Page 32
3 x 14 =
base 60.. wow lol
This is also a special case of the polarization identity: en.wikipedia.org/wiki/Polarization_identity#Real_vector_spaces
Oh I didnt see you mentioned it at the end. well done!
Never clicked on a video so fast. Love your graphics work!
Same
I hadn't even heard about this method, although I'm a 8-bit demoscene coder. I've usually just used logarithm tables when in need of fast multiplication.
For integers, the divide by 4, in binary, is simply a right shift by 2. Using this trick, even the look-up table could just be the squares of the numbers instead of the truncated quarter of their squares.
but... doing a bit shift is much slower than not doing it!
@@InigoQuilez Constant right bit shift of 2 is simply not connecting last two bits of the wire. So, doing it as good as not doing it. Right? :)
Sure, but the video focuses in software implementations. For a hardware implementations there are dedicated algorithms. Bit that's a whole different rabbit hole.
@@RajeshGanesan92 many cpus without multipliers also don't have barrel shifters, a shift of more than one bit is a big hit
@@InigoQuilez Sure, that's true! Also, why does a look up table for int8 need 511 elements? Doesn't 256 elements suffice? That way we would only need 0.5 KB.
Intresting & thats a way of thinking by do coding. So be creativ and teak the other way. Some of agiptical logic ar to impresiv and easy to in the end.
Thanks foe teatching us by bennoH.
& By the way, dit u have testing or doing coding in Vulkan SPIR-V Shaders and can you do a free online curs for us. Becus i think it's the next generation of schaders.
Base 60? Jesus.
I was not prepared for the last part
Thank you for yet another great video. I love your content!
This was beautiful
Great as always!
But what is 3×14?
42
I'm afraid I don't have an enormous enough supercomputer that can compute that one.
@@InigoQuilez I wonder whom to contact about renting some CPU time on the one we're standing on?
2:11 42
There might be more. See if you find any
Awesome video! The generalization of this identity to dot products is also called the polarization identity: en.m.wikipedia.org/wiki/Polarization_identity