LMD Async Tutoring

[LMD]

@Elliot

@LMD

or(x, y); 1 - ((1 - x) * (1 - y))

Yes. Try simplifying this with standard arithmetic.

Do you mean a way other than how I simplified it here?

[Elliot]

That’s good

[LMD]

@Elliot

And you can find another one using a comparison operator.

I got this solution for or(x, y) that uses a comparison operator:

x + y > 0

Is there also a solution that only uses a comparison operator(s)?

[LMD]

Maybe that needs brackets. But I’m not sure of the order of operations with comparators. This is what my solution meant:

(x + y) > 0

[Elliot]

@LMD

Is there also a solution that only uses a comparison operator(s)?

No

[LMD]

@Elliot

There are also other solutions for or(x,y). Try to find another one with integers with no negative numbers, subtraction or non-linear terms.

I’m confused about what linear and non linear terms are. You say:

@Elliot

One is linear (no term like xx or xy) and thinking about number line transformations can help find it.

Is multiplication in general non-linear?

[Elliot]

Try looking it up

[LMD]

I did briefly before I asked but I only found things referring to linear and non-linear equations, I couldn’t find reference to nonlinear terms. Now googling ‘nonlinear term math’ returns more about equations. I found some things about the concept of multiplication being bilinear when googling ‘is multiplication linear’ but most things were over my skill level and I couldn’t make sense of them. I’m still confused.

[LMD]

Oh, I’ve found some info relating to linear terms:

A linear term has a degree of 1. For example, 5x, -2x and x are all linear terms. These terms are x to the first degree (X^1), where the “1” isn’t written (because any number to the first power is just that number).

Terms that are not linear are called non-linear terms. The most common one you’ll come across in calculus is the quadratic term.

So I can see why xx is not a linear term: it is x to the second degree or x^2. I’m not sure why xy would be a non-linear term. Unless x and y are the same value! If x = 1 and y = 1 then xy is 1^2?

[Elliot]

Read first paragraph at Degree of a polynomial - Wikipedia

[LMD]

Okay. From that paragraph:

The degree of a term is the sum of the exponents of the variables that appear in it, and thus is a non-negative integer.

The sum of the exponents of the variables x and y in the term xy is 2. So if a linear term has a degree of one, then xy is non-linear. So the answer to my question:

@LMD

Is multiplication in general non-linear?

is no. It is the degree of a term not being 1 that makes something non-linear, not the fact that there is multiplication happening.

[LMD]

@Elliot

There are also other solutions for or(x,y). Try to find another one with integers with no negative numbers, subtraction or non-linear terms.

No luck so far finding a solution that meets this criteria. I’ve been trying to apply the things about number lines to it, but I’ve got no good ideas. I think I’ve spent too long on this though I haven’t kept track of the time.

[LMD]

@Elliot

The sum x+y is 0, 1 or 2.

You know the goal for what you want to transform it to in each case:

0 → 0
1 → 1
2 → 1

If you think about it with two number lines, the left numbers correspond to the top number line and the right numbers to the bottom one.

What mathematical operation could help here? What conceptually do you need to do?

What conceptually do I need to do?

In that mapping, all numbers that aren’t 0 map to 1. All positive numbers map to 1. The solution x + y > 0 conceptually does this. It makes all positive numbers map to 1. How do we do something similar, but just with basic arithmetic?

1 is the multiplicative identity. Any number divided by itself equals one (except zero). But we can’t use fractions.

anything to the power of zero is 1. But then 0 maps to 1.

how can we check if something is positive using only addition and multiplication?

I’ve scrolled down to see further discussion.

Okay, I hadn’t considered integer division. I don’t have practise thinking about integer division so I’m gunna practise some more see if I notice anything.

3 / 6 = 0
3 mod 6 = 3

6 / 2 = 3
6 % 2 = 0

12 / 7 = 1
12 % 7 = 5

45 / 4 = 11
45 % 4 = 1

2 / 1 = 2
2 % 1 = 0

1 / 2 = 0
1 % 2 = 1

0 / 2 = 0
2 / 2 = 1
1 / 2 = 0

0 / 2 = 0
0 mod 2 = 0

0 mod 2 = 0
2 mod 2 = 0
1 mod 2 = 1

Stopping for today. Stuck here.

[Elliot]

@LMD

It makes all positive numbers map to 1. How do we do something similar, but just with basic arithmetic?

Hint: you don’t need to map all positive numbers to 1 to solve this problem. You only need to map a few specific numbers, which is easier.

There are more hints in the Eternity topic.

[LMD]

@Elliot

When you look at the n/10 number lines, can you find any section which matches your goal?

Okay as soon as I saw this prompt I knew how to do it.

1 / 10 = 0
2 / 10 = 0
3 / 10 = 0
4 / 10 = 0
5 / 10 = 0
6 / 10 = 0
7 / 10 = 0
8 / 10 = 0
9 / 10 = 0
10 / 10 = 1
11 / 10 = 1

These last three give me the outputs I want:

9 / 10 = 0
10 / 10 = 1
11 / 10 = 1

so (x + y + 9) / 10 would work.

But I think a smaller one would work. would ‘/ 3’ work?

1 / 3 = 0
2 / 3 = 0
3 / 3 = 1
4 / 3 = 1

so (x + y + 1) / 3

or(1, 1): (1 + 1 + 1) / 3 = 1
or(1, 0): (1 + 0 + 1) / 3 = 0

okay no

3 / 2 = 1
2 / 2 = 1
1 / 2 = 0

Okay that’ll do it:

or(x, y) = (x + y + 1) / 2

or(1, 1): (1 + 1 + 1) / 2 = 1
or(1, 0): (1 + 0 + 1) / 2 = 1
or(0, 1): (0 + 1 + 1) / 2 = 1
or(0, 0): (0 + 0 + 1) / 2 = 0

[LMD]

@Elliot

You can look for another solution for or(x,y) now which uses remainder.

This is my working. In it I happen upon a remainder solution to xor. I’m still stuck on a remainder solution to or though.

1 % 5 = 1
2 % 5 = 2
3 % 5 = 3
4 % 5 = 4
5 % 5 = 0

I want to map:

0 → 0
1 → 1
2 → 1

5 % 1 = 0
5 % 2 = 1
5 % 3 = 2
5 % 4 = 1
5 % 6 = 5
5 % 7 = 5
5 % 8 = 5
…

6 % 1 = 0
6 % 2 = 0
6 % 3 = 0
6 % 4 = 2
6 % 5 = 1
6 % 6 = 0
6 % 7 = 6
…

3 % 1 = 0
3 % 2 = 1
3 % 3 = 0
3 % 4 = 3
…

So a first number mod a second and larger number outputs the first number

5 % 1 = 0
6 % 2 = 0
7 % 3 = 1
8 % 4 = 0
9 % 5 = 4
10 % 6 = 4
11 % 8 = 3

3 % 1 = 0
4 % 1 = 0

0 % 2 = 0
1 % 2 = 1
2 % 2 = 0
3 % 2 = 1
4 % 2 = 0
5 % 2 = 1
6 % 2 = 0
7 % 2 = 1
8 % 2 = 0
9 % 2 = 1

Okay so using ‘% 2’ can check if something is even or odd. That means you could use it for xor.

xor(x, y) = (x + y) % 2

Okay, so I am conceptually trying to do the same thing as with division. Mapping 0 to 0, and 1 and 2 to 1. The hint was to try n/10. That made me see that anything under 10 output 0 and anything above output 1. So I want a way that I can use remainder do the same thing. Can I use remainder to check primes? I know that 1 and 2 are both primes. if there was a prime check function called ‘prime’ that output true when prime, i could do:

0 prime 0
1 prime 1
2 prime 1

When is something a prime? When it has no factors except 1 and itself. I think I would maybe need to recursively check that each number below the input wasn’t a factor though. What other things maps 0, 1, 2 to 0, 1, 1?

A remainder function subtracts the second number from the first number until it cant and then returns the remainder.

If i could multiply 0, 1, 2 by something, that would spread them out across the number line, keeping 0 at 0. But they’re then all scaled by the same amount.

Hmm. Stuck for now.

[LMD]

I’ve continued in the Eternity topic and found their remainder solution for or(x, y) which is:

• 1 mod (x + y + 1)

This works because 1 mod anything higher than 1 will output 1.

I could’ve realised this before when I noticed that:

…a first number mod a second and larger number outputs the first number

So I could’ve seen that if had 1 mod 1 i’d get 0, and 1 mod anything higher would return 1. Hmm. I’m not sure why I missed that.

[LMD]

@Elliot

You can find another one if you want. You could also do xor(x,y).

I got xor above: (x + y) mod 2.

Okay. Another remainder one. I can try.

So 1 mod x checks if x is greater than 1. In this configuration it functions as a ‘greater than’ comparator that outputs 0 or 1.

In my solution for xor, x mod 2 functions as an even number checker, checking if x is even.

or(x, y): (x + y + xy) mod 2

1, 1: (1 + 1 + (1 * 1)) mod 2 = 1
1, 0: (1 + 0 + (1 * 0)) mod 2 = 1
0, 1: (0 + 1 + (0 * 1)) mod 2 = 1
0, 0: (0 + 0 + (0 * 0)) mod 2 = 0

This is like the remainder xor expression, but it makes the case where both inputs are 1 sum to an odd number by adding xy (which equals 1 only when the inputs are both 1)

[LMD]

@Elliot

@Eternity

or(x,y) = (x+y+xy) remainder 2

Yeah that’s good. You can find other versions if you want but you can absolutely move on too.

Oh cool I got it.

[LMD]

@Elliot

Implementing arithmetic using logic is kinda hard and unnecessary. If you want to look at that, there is lots of stuff online if you search terms like “half adder”. I don’t really recommend this stuff but maybe watch a 15 minute video to get a rough idea of what it’s like and see how much it interests you. Some of this stuff is covered in Feynman’s lectures on computation (I like that book but it’s technical and unnecessary) and I’m sure it’s in many textbooks.

Let me know how that goes and what you want to do. We could potentially move on to grammar.

I watched this computerphile video on xor and the half-adder:

XOR & the Half Adder - Computerphile

I liked idea of the inputs of the two different gates of the half adder being in parallel and so being fed the same inputs. I like electronics, and have some experience with basic analogue circuits. I think for now though I’d like to move on to something different.

I skimmed the first couple pages of the introduction of the Feynman Lectures on Computation and I think I’d like to read it.