computers suck at division (a painful discovery)

computers suck at Division I realized this when I was coding some arm assembly trying to solve what I thought was a relatively simple problem The Prompt was to write a function in assembly of course that would convert a Fahrenheit temperature into Celsius the equation for this is quite simple the degree is in Fahrenheit minus 32 times 5 divided by 9 yields the degrees in celsius this seems simple enough but it quickly turned into something that was much more complicated as I was writing the code setting up the stack and making room for local variables was an easy and familiar task next I did the first part of the equation subtract 32. great success I felt like I was on my way to a quick low-level Victory but here I encountered my first problem the fraction because 5 over 9 is not a whole regular number I would have to use the arm processor's floating Point Unit or FPU to do floating Point math to get my answer the problem was that not all arm processors have an FPU and without an FPU I would have to rely on lib C's floating Point approximation libraries to just do the math for me and that felt like cheating surely there is an easier way instead of treating five over nine like a fraction I decided to treat it like two separate operations first multiply by five and then divide by nine finally the light at the end of the tunnel was beginning to show and this is where the story takes a slight turn I quickly learned that arm cores didn't have a division instruction until 2004 and that most of the smaller cortex M series processors still don't support signed or unsigned division how is this possible did the algorithms executed by those chips just never include division after banging my head against a wall for a few hours I decided to write the function in godbolt and see what the assembler produced for the arm solution what stuck out to me was this magic number here instead of doing a division operation my input was being multiplied by this large constant instead of just accepting that compilers and computers are Blackmagic with deep mythical undertakings I dove deeper it turns out that the number here is being used to do what is referred to as fixed Point multiplication wait multiplication I thought we were doing division hold your horses we'll get there the algorithm we're being asked to do was to multiply by 5 and then divide by nine because we can't divide by nine because there are no divide instructions what we could do instead is multiply by one over nine the issue with one over nine is that it is not a whole number and again we can't use floats this is where fixed Point representation comes into play we can represent 1 over 9 as a binary fixed Point number like this one over nine is an infinitely repeating binary pattern but we can approximate the value to a certain point by truncating the pattern at this point here because we can't store the decimal point in binary like we can with floats we'll just make the decimal point implied by scaling the number we scale the number by Shifting the decimal point in binary to the right by multiplying it by a very high power of two the exact power of two that you use depends on the accuracy that you want from the number and the number of bits you have to work with so boiling that all down this number here is the result of 2 to the power of 33 divided by 9 and then we add 1 to approximate for the data that we lose by truncating the repeating pattern arm with this power I felt like I was finally ready to solve the problem because I didn't want to cheat and just use the number they gave me I decided to use my own magical constant using the same mathematical principle I use this number here which is just 2 to the power of 32 divided by 9 plus 1. in theory it would provide the same results with just a bit less accuracy at higher input values but working with degrees I wasn't too worried about that finally I could write my code first I subtracted 32 from my input number next I multiplied it by five and finally to approximate the division by 9 I would do a 64-bit multiplication where the result of the operation goes into two separate registers here the high 32 bits are in r0 and the low 32 bits are in R4 because the high 32 bits are in r0 we don't have to do any bit shifting in r0 by default contains our answer using this harness I'm able to check to see if my function converts 86 degrees Fahrenheit to the correct answer of 30 in Celsius we try it out and great success after I finished the problem I wanted to figure out why arm chips didn't have divide instructions and it's all kind of odd to me after some digging the answer seemed pretty straightforward division is such a slow algorithm that chip designers typically create a separate set of circuits in the chip to accelerate the operation these circuits take up a ton of silicon dye space and are extremely expensive to make because of this arm decided they just weren't needed and for certain variants of the cortex m0 they still don't hey guys thanks for watching I really enjoyed making that video if you liked it as well do me a favor hit like hit subscribe and then go watch this video about how I hacked my own server using a buffer overflow with strings I'll see you there

Channel: Low Level Learning

Views: 1,645,657

Keywords: arm division, fixed point multiplication, hackers, security, binary, hexidecimal, raspberry pi, pico, rpi, microcontroller, arduino, maker, craft, hobby, electronics, wires, temperature, safety, project, board, electric, leds, led, thonny, python, micropython, os, ide, onewire, ds18b20, circuitpython, review, launch, measure, probe, rp2040, specs, specifications, how to, guide, programming, Pico emulation, retro games raspberry pi pico, etaprime, eta prime, raspberry pi pico, arm cortex m0+, low cost

Id: ssDBqQ5f5_0

Length: 5min 9sec (309 seconds)

Published: Thu Dec 01 2022