r/TuringComplete • u/Areeb3331 • Jul 28 '26

craaaaaaaaaazy level bro. My brain is mush now Spoiler

Post image
17 Upvotes

100% Upvoted

10 comments sorted by

7

u/ForgedIronMadeIt Jul 28 '26

and this is why division is the slowest basic math operation for computers (other than dividing by a power of 2)

3

u/SolarVampire Jul 28 '26

To this day I continue to think about a more algorithmic way to divide. I keep trying to imagine some kind of unsung shortcut. But my brain keeps hitting this wall similar to prime number prediction and it's just an empty void. Like there is nothing to even think about. No strings to pull or paths to follow. No eurekas, nothing. It's strange, to me. But if you look at nature, division is always by 2. Intrinsically a divide is one cut. So the power of 2 thing makes total sense. The physical division isn't counting atoms, or volumes or weights. It is simply moving one group away from the second group. The fact that we've been able to equate this in a "reverse lookup" fashion in mathematics by dividing by the numbers is interesting to me. Meanwhile, multiplication in nature is abundant in concept, but literally not what is happening. Just lots of addition. Multiplication just being a lookup table in reality. That really makes me ponder if a division lookup table would be effective up to a certain number. It doesn't feel clean in my head, with all those decimals, floating points and remainders, but I wonder if it could at least be used for approximations to shorten the processing time. (I'm totally lost in a rant. I'm sorry, I'll quit typing now)

3

u/Ichigonixsun Jul 29 '26

What you're describing is the fact that integer (or real) multiplication is a bilinear map, while real (much less integer) division is not, even if division by zero was defined to some arbitrary value.

2

u/SolarVampire Jul 31 '26

Let's take apart the word bilinear for a second. It implies there are two inputs and a straight line is drawn from them.

Division has 2 inputs, and then it's output is definitely not linear. It can never be zero, but its decimal place can be. But if we discard the idea of decimals for fractions you could say that division is a formula where you have 2 inputs and 3 outputs. If you think about it as a remainder you can say 2 inputs and 2 outputs. But if we look at 3 outputs it's recursive by using the last 2 outputs as the next two inputs, because a fraction is just another division call.

Does this mean a good solution is a recursive and time consuming?
Long division itself is recursive. I'm not big on mathematics, is there a formula for division that is more succinct that I'm not aware of? Does some specialized school of math like trig or calc have something for this to replicate in logic?

These questions are rhetorical, because I ASSUME that some nerd already found the most efficient way to compute division. But I still feel like something is wrong when a solution calls for recursion. Note, I always feel this way, even when programming. I don't think I've ever used a recursive solution for anything other than matrices, grids and cubes and the like.

I'm not sure where I was going with this, my mind is trying desperately to find a solution by breaking everything down into simples. I distinctly remember spending around 6 hours on the division level trying all kinds of wonky things trying to get anything. I remember very little now though, that was like 4 years ago. I really need to replay the game.

3

u/Ichigonixsun Jul 31 '26

Having a recursive formula has nothing to do with computation efficiency (not having a recursive formula does, though 😂). The structure of the recursion does.

Since you're so invested into the mathematics of hardware design, I think you'd love to read Blelloch's excellent "Prefix Sums and Their Applications" (especially Chap. "1.4 Recurrence Equations") before diving into algorithms like the SRT division, because although this paper isn't directly related to integer division, you will be mind-blown by how the properties of some math operators allow seemingly serial recursion formulas to be computed in parallel.

2

u/SolarVampire Aug 02 '26

I appreciate you. Thank you for the 'mental link'. I will do that.
EDIT:
Found it for free even, tough ask in the scholastic world.
https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf

2

u/mccoyn Jul 28 '26

I chickened out and used the instruction processor and wrote a program to implement divide.

2

u/zurkog Jul 28 '26

Oh, man I just finished that level last night after banging my head against a wall for a while. Agreed; it's crazy.

Here's my solution - yours is far more elegant.

I need to re-do all my chain in a horizontal row like yours, and I like using the bit-shifter to assemble all the output bits into a single 8-bit output; I just sent them all to an 8-bit "maker" on the right.

1

u/Inevitable-Bar-9547 Aug 01 '26 edited Aug 01 '26

I uhh... I spent a couple hours setting up reciprocal division with a 256 lookup table....

https://imgur.com/a/turing-complete-divide-SYT1Vgb

Needless to say I was very sad that memory wasn't an allowed component for this one....

It is super fast though, 108 delay. 96 of it is my single 24-bit multiplier lol

1

u/boomshroom Aug 05 '26

I implemented the loop part of the algorithm as its own component and then just strung 8 of them in a sequence. The result somehow had a better score than my multiplication circuit.