Unsigned Less?

[ThemePark]

I've become completely stuck on both Unsigned Less and Signed Less. I've had a couple ideas on how to solve them, but I just don't see a way to complete them.

I can easily use XOR to find the first differing bits, in order from MSB to LSB. But that requires that I ignore all outputs after those bits have been found, meaning I need something that's neither on nor off, a null. Otherwise I'm just stuck with signals from the lower bits that may also be on.

Another idea I've had is to first check if the bytes are equal, and then checking the sign bits. But like with Unsigned Less, I could have two bytes with the same sign and still have to check all the lower bits.

So I'm not really sure where to go from here.

[Arnavion]

For Unsigned Less, under what conditions is A < B?

If A7 < B7, then A < B

If A7 == B7 && A6 < B6, then A < B

If A7 == B7 && A6 == B6 && A5 < B5, then A < B

...

So putting it all together:

A < B = (A7 < B7) || (A7 == B7 && A6 < B6) || (A7 == B7 && A6 == B6 && A5 < B5) || ...

Since An and Bn are single bits, there are four possible pairs of values. For which of these four pairs will An < Bn ? How can you encode these pairs with gates?

What gate can you use to compute An == Bn ?

---

For Signed Less, is there any way you can reuse the solution for Unsigned Less? Recall that a signed number is just an unsigned number that pretends to be 128 smaller than its bit representation. How does that affect the above calculation? (Hint: Only a very tiny part is different.)

[wbradley]

For Unsigned Less, the generation of "these single bits are the same" signals and combining those into a chain of "all higher bits are the same" is the key to making sure evaluation stops at the first differing bit.

Opprinnelig skrevet av Arnavion:

For Signed Less, is there any way you can reuse the solution for Unsigned Less?

Key questions you should be asking yourself here are:

- Does your solution to Unsigned Less work on signed numbers when their sign bits are the same?

- Does your solution to Unsigned Less work on signed numbers when their sign bits differ?

[ThemePark]

Opprinnelig skrevet av wbradley:

For Unsigned Less, the generation of "these single bits are the same" signals and combining those into a chain of "all higher bits are the same" is the key to making sure evaluation stops at the first differing bit.

Question: But how do I make the distinction between the chain result and the differing result? That's what I can't comprehend.

If I use XOR on each pair of bits, I get an On signal as soon as I hit the first differing bit, and I can use NEG on the first byte and then AND on that pair of bits to get the result. But if the first bit is not less than the second bit, it gives an Off signal, the same as if I've ANDed all the previous pairs of bits. And even if I use a component to switch between two signals, or turn a signal on or off, I still don't see how I can distinguish between two results with different meanings, but that both produce an Off signal.

[wbradley]

This isn't how I approached this problem, and this isn't at *all* optimized for nand count or delay, but here's a straightforward approach:

https://imgur.com/a/DNUgK1J

You're XNOR'ing pairs of bits (is this pair of bits the same?) and AND'ing all of those results together as the chain cascades upwards (are all previous pairs of bits the same?). For each individual XNOR gate, you can invert that result (is this pair of bits different?) and AND that with the chained result up to that point (is this pair of bits different and all previous pairs are the same?). The first stage where the bits differ will shut off the cascaded results chain (as the XNOR evaluates to 0 there) so the remaining AND gates will all evaluate to 0 as well.

[ThemePark]

Thanks, that helped me finish the level. With my initial idea and your comments, I was focusing on somehow having to chain the horizontal AND gates in your example, I didn't realize I needed a whole row more of gates chained to each other and the XOR in my example.

Signed Less should be easy enough to solve now, once I've had a break.

[Hippiecab]

I solved the unsigned less problem a different way.
I realized that by utilizing the byte adder's carry bit and an extra full adder, i could construct a 9 bit adder, thereby being able to extend the input bytes to be 9 bit numbers. I could then negate the second input with twos complement and add the two numbers together. By looking at the last bit of the sum I could then see if the second input was larger (making the sum negative)

[Dante]

For both signed and unsigned I kind of brute-forced what I think is the optimal solution.
I did A+(-B) and considered 4 bits:
A high
B high
A-B high
A-B carry
Then I draw a truth table and figured out a possible circuit that satisfies this table.
https://i.ibb.co/Sr5ZJBz/Screenshot-20211120-215936.png
https://i.ibb.co/WPMM4Qt/Screenshot-20211120-215734.png

[Dante]

Now after unlocking NAND costs and delays I reworked my old solution, now with 37 NANDs and the delay of 8.
https://i.ibb.co/8MPSJTL/unsigned-less.png
The signed less is the same, except that we invert the high bit.

[Arnavion]

Optimal is NAND = 19, delay = 6, FYI.

[tonym1972]

The simple (he says whilst drinking alcohol) is to suspect the games author wants us to build a magnitude comparitor. The level Equity had us build the first part, this therefore is the second.

So to build a magnitude comparitor we need a diode, and guess what we don't have!

But we can fake it!

We need to solve for every bit NOT A AND B which we can do with the 8 bit components, however we need to combine that result in a sane way. We do that thus we also calculate A AND NOT B, A XNOR B with these 3 results we can construct a switch matrix where NOT A AND B outputs a logical 1, A XNOR B copies the previous result and A AND NOT B outputs a logical 0.

If someone wants a screenshot of the switch matrix, let me know and I'll make it happen.

[tonym1972]

As I never reply to my steam messages
https://steamcommunity.com/sharedfiles/filedetails/?id=3092590711
is the screenshot.

[tonym1972]

Okay fine, as you didn't ask nicely, the signed version!

https://steamcommunity.com/sharedfiles/filedetails/?id=3092630648

we all good, you all is happy?
:_) ;;)

[ben man]

can someone help me here? All of these solutions either no longer work, or dont explain them well enough for me to even slightly understand

[UnsignedRobin]

Does this help? It's a different approach, though...
https://ibb.co/kXRcyqC

I don't want to over explain - feel free to ask further questions.

[tonym1972]

@ben man
My apologies if my posts in this thread didn't explain my approach to the problem, let me try and rectify that now.

My solution is based on a device known as a "magnitude comparitor" https://en.wikipedia.org/wiki/Digital_comparator
In very simple terms it computes 3 terms...
An XOR Bn :- if FALSE both bits are equal
(An XOR Bn) AND An :- if TRUE An > Bn
(An XOR Bn) AND Bn :- if TRUE Bn > An

Where "n" is the bit position.

This information for all 8 bits is feed into a switch network, to propagate a signal reflecting if A <=> B (well mostly, A == B isn't a requirement of the tests, so isn't really calculated as an output).

So that's how the unsigned version works, the signed version has a short cut...
A7 XOR B7 if TRUE then....
A7 AND (NOT B7) = TRUE then A < B
B7 AND (NOT A7) = TRUE then B < A
Otherwise we stick with the unsigned magnitude comparitor to figure out the solution.

Hopefully that helps you move forwards.

EDIT
-----
just spotted my screenshots hidden behind a spoiler tag arn't accessible... so, no spoiler tag versions.
https://steamuserimages-a.akamaihd.net/ugc/2306467913482183565/4F23A86A00F6F5CC600B58AF3C57F7E7A6B81504/?imw=5000&imh=5000&ima=fit&impolicy=Letterbox&imcolor=%23000000&letterbox=false
https://steamuserimages-a.akamaihd.net/ugc/2306467913482419522/FED9ACB5B999DFD261F59606698A9C0619E3C69D/?imw=5000&imh=5000&ima=fit&impolicy=Letterbox&imcolor=%23000000&letterbox=false