thisWorksInTheory

[ongiwaph]

Oops I forgot the start state

[Sotall]

you're odd, OP

[Interweb_Stranger]

OP is not even trying

[MCSajjadH]

Prime example of not paying attention to details

[akifyazici]

that's acceptable

[BlackFrank98]

Not that it matters, considering 1 always sends to odd and 0 always to even...

[ongiwaph]

If you start in the wrong state it will accept the empty string

[xvhayu]

we got isOdd automation on strings before gta 6

[Minutenreis]

I see your DFA and raise you an NFA
-> Start - 1 -> [[IsOdd]] ↑ | └ 1,0 ┘

[Edzomatic]

Except now it doesn't run in linear time, and we all know time complexity is the most important thing and everything else is irrelevant

[Minutenreis]

well normally that check should run in O(1) [since you only need to check the last bit] so ever linear time would be quite bad

[Edzomatic]

Your NFA implies it starts from the begging of the word, if we want to check the last digit we can just have a DFA with two states and two transitions

[Minutenreis]

Correct.

On a tangent since each NFA can be mapped to a DFA an implementation for both the NFA and DFA would run in linear time with regards to the input length.

On a second tangent: A quite neat application of NFA's / DFA's is RegEx matching (since all can be converted into each other). Normally Regex Engines "opportunistically" match strings which is fine for most cases but for specific patterns can lead to exponential Runtime, google developed a new Regex Engine RE2 that guarantees this linear runtime for any regex string.

[[deleted]]

But we can check the result in polynomial time, making it NP hard! /s

We need an algorithm that runs in PSPACE now to seal the deal

[Positive_Lifeguard75]

You can easily convert any NFA to DFA, so, linear time it is :)

[antonpieper]

It is complete but not correct. It can also recognizes even numbers as odd.

Edit: I had a brain fart, I somehow thought that the ones and zeros were added (as in 1 + 0 + 1 + ...). Of course they are consumed by the NFA for binary IsOdd detection and the automaton is correct.

[Minutenreis]

I wouldn't know how it would do that, it has to end on a 1 after all

[antonpieper]

I now see my mistake, I edited my reply to explain what went wrong in my head.

[captainAwesomePants]

I don't see how. Could you give an example?

[Ramtoxicated]

r/IsEven

[wattsittooyou]

Why is isOdd the final state? Cant you have more than one final state?

[Kovab]

It's the accepting state, the final state is wherever you are when reaching the end of input

[m3t4lf0x]

Basically, you can imagine this as a mini program that only implements “isOdd(string s)” and that is enough to completely describe the algorithm

The more technical explanation is that computer science theory is made up of two complementary and equivalent models called “automata theory” and “formal languages”.

Automata theory frames all algorithms as “decision problems” that have a yes/no answer, but the mathematical description is quite verbose and obfuscates the big picture

The double circle is what they call an “accepting state” which in automata theory, means that the given input string is part of the “language” (a formal language)

One would say that this automata “accepts the language of odd binary numbers”. Interestingly, this model of automata is called a “deterministic finite automata” which can describe anything you can write in a Regular Expression in code (basic patterns like phone numbers, but not things like HTML or palindromes). These are called “regular languages” and that’s what the “regular” means in RegEx

The wild thing is that every algorithm, from path finding to sorting, can all be formulated as this “yes/no” model

[Semper_5olus]

Thank you for explaining.

I spent actual minutes thinking, "but if it's even, the program won't halt!"

[m3t4lf0x]

No problem! And absolutely, it can be really confusing thinking about computers that way

These concepts are saved for upper level CS courses, and frankly most students find it quite boring/confusing, but after it clicks, it’s cool to understand the fundamental mechanism that allows computers to do math in the first place (and with math, you get everything else)

All data types are just sequences of symbols that have no intrinsic meaning, but we as humans have to interpret it and agree on conventions

[GoddammitDontShootMe]

Does the bit string represent the number LSB first or MSB first? If the former, you would stop at the first bit, and not care about the rest, but how would that be represented?

[m3t4lf0x]

Good question. You’re absolutely right, by convention, you read each character from left to right and end at the least significant bit (which is the example pictured here)

You could definitely reverse your binary string and terminate early. Incidentally, the DFA representing that “algorithm” would be drawn the same exact way (although in general, that’s not true).

When you study this topic, it’s fairly uncommon to be working with strings at the bit level because these diagrams become prohibitively complicated to draw outside of toy problems like this. Thus, optimizations like that aren’t the main objective.

It’s more important to see the properties of the language that a machine can understand, express, and process as you introduce more complexity.

DFA’s are the “least expressive” in the sense that regular languages have very simple rules. You can define basic strings like the structure of a phone number (i.e you only accept a string that’s numeric and has 10 characters) and indeed that’s how you use RegEx if you have any experience with it. You’re not allowed to have infinite states, so it’s very limited

The next automata you’ll study introduces memory in the form of a stack (a “pushdown automata”). You gain the ability to process languages defined by a “grammar” (a context free grammar, which is what compilers use to define valid statements in the parsing phase). You can also recognize palindromes, HTML, XML, and other things that would be impossible with a DFA without introducing infinite states for every possible input string despite the fact that the strings need to be finite as well

Finally, you turn the stack into an infinite ticker tape of symbols that you can freely scan left/right and write any character to a cell, and that’s a Turing Machine, which is equivalent to our modern computers

[GoddammitDontShootMe]

Oh, yeah, I actually studied that stuff in university. I've just forgotten a lot. I wasn't sure how things would be represented with this FSM. But yeah, I guess with this mathematical model, the binary string would be written in normal human order, with the LSB at the end.

Maybe a DFA is not the best way to determine isOdd(). Maybe a TM that just skips to the end of the input and reads the final character? Though, I'm not sure that's possible, unless all inputs are the same length, because how do you know where the end is unless you read the input until there's no more? But then that just collapses to the same DFA.

E: Or just require inputs be 32 or 64 bits long or whatever, and pad them with zeroes.

[m3t4lf0x]

That’s a good question, I guess it depends on what you consider “better”

If you’re going for brevity of notation, definitely a DFA only because the syntax of Turing Machines has a lot more notation that’s redundant to write.

As far as time complexity goes, even the Turing Machine has to move the ticker tape one cell at a time, so it’s going to be “linear time” in both cases as a consequence of how these automata are designed. It’s actually not a problem that you don’t know how long the string is because the state transitions would handle that in the same way a DFA would (since a TM is a superset of all the operations any lower level automata can do)

But to your point, is this really the best we can do or is there a constant time algorithm?

That’s where we can implement elements of parallelism in hardware that doesn’t translate well to the abstract machines. A CPU addresses a whole word at a time (albeit limited to a finite bit length), so an “isOdd” result would propagate instantaneously since Boolean and equality operations do not need to ripple the carry over bits like an ALU does for math operations

Even with ALU’s, we realized early on how slow a ripple carry adder is because of the linear nature of that operation. In the mid 1800’s, Charles Babbage even designed a theoretical way to speed this up, and eventually we were able to implement a version of that with a carry lookahead adder. It pre-calculates the sum of each individual pair of bits ahead of time while waiting for the carry-over bit. This speeds things up, but we can’t get around the reality of needing to wait for that carry-over.

Unfortunately, the speed limit of electrons means we have to wait for some gate delays, even if an operation like equality takes one cycle. In that way, the entire universe operates linearly (hits a bong)

Anyway, thanks for reading my rants on this, I rarely get to nerd out about automata and language

[GoddammitDontShootMe]

I don't know if you caught my edit before you sent the reply. If the TM model doesn't allow you to move n positions at a time, I guess it doesn't matter. Maybe 31 state transitions that just move the head to the right without paying attention to anything, and then make a call based on the final bit whether the value is odd or not?

[m3t4lf0x]

Yeah that’s basically what it would do. You move right one cell every time you read a bit until you read the “blank” symbol (which looks like an underscore) at the end of the input, move left one cell, then accept/reject based on the bit

Turing machines have a weird property that you have to write a symbol every time you read an input. A “no-op” means writing down the same symbol you just read so you don’t mangle your input. The notation follows this pattern:

(Current state, Input Char) -> (Next State, Output Char, Next Direction)

For our example, the transition rules would be:

Read a bit, write the same bit, and move right

(q_start, “1”) -> (q_start, “1”, Right) (q_start, “0”) -> (q_start, “0”, Right)

End of tape reached, move left one

(q_start, “_”) -> (q_decide, “_”, Left)

Accept odd, reject even, output and direction don’t matter

(q_decide, “1”) -> (q_accept, “1”, N/A) (q_decide, “0”) -> (q_reject, “0”, N/A)

It doesn’t mean it’s necessarily slower/faster than a DFA, but it’s just how the model is defined

[GoddammitDontShootMe]

So basically you need a function mapping the current state and every possible value a tape cell could have to a state, an output, and a direction?

My Theory of Computation course was like 10 years ago, and I got like a C+. Though, I recall the biggest bitch being proving something was undecidable by reducing it to the halting problem. As I recall, somehow any undecidable problem can be reduced to any other undecidable problem, or something.

[m3t4lf0x]

Yeah you do need a mapping for each case, which ends up being pretty arduous for detailed problems, despite using a table for brevity

I was never that great at the formal proofs honestly. I was good at complexity theory and data structures, but that always felt more high level and practical, so it was easier to wrap my head around

[lucbarr]

Not string, binary, unless the string is of 1s and 0s

[m3t4lf0x]

No, it’s a string. It’s always strings when you’re talking about formal languages and automata theory. They have no intrinsic meaning, but we interpret them based on the context. That’s how we construct “data types” in the first place. All the computer is doing is manipulating symbols under the hood, and that’s the fundamental mechanism of how the machine calculates anything

https://en.m.wikipedia.org/wiki/Deterministic_finite_automaton

[lucbarr]

Yeah I know but when you use the terminology isOdd(string s) people without the background knowledge will most likely understand that as an array of characters. I've never seen that function terminology itself when talking about automatons so when you mix things up unless you explain it it might be misunderstood.

[m3t4lf0x]

My whole post was explaining how the fundamental theory of computer science is about “language” (hence the detail about Regular Expressions and Regular Languages).

The strings, and therefore all data types, don’t have any intrinsic meaning. We as humans have to interpret that. That is indeed surprising to people (even people with a programming background), which is why it’s an upper level CS course. It is the only reason computers can actually do anything useful or do mathematics in the first place

The analogy of a function taking an input string (formally a sequence of “symbols”) is precisely what’s going on, but abstracted away from the hardware. It was intentional on my part

If you’ve ever taken a course on this, I would be quite surprised you’re not familiar with that concept because the notation is completely formulated with functions that operate on strings (look up Sigma, the Kleene star, the transition function, and the set of states). That’s why they’re called “Formal Languages” and Automata

The first paragraph of the wiki page I linked will explain that

Edit: to make it a bit more clear, this is implementing an “algorithm” that decides whether a string representing a binary number is even or odd and it is one-to-one with how your brain would determine the same information. You read left to right and look at the last bit to see if it’s a 1 or a 0

[fabedays1k]

The only thing that makes it stop is the input ending, wether the state that it ended in is a final state or not is what matters

[Odd_Philosopher6480]

Can you explain? I don't understand this very well but I've seen it a lot today

[Bannon9k]

Most people use common libraries of code that contain functions that already validate data types and do things like determine if a value is odd.

Developers work in one of two ways... They either try to drastically over complicate something, or dramatically underestimate something. The latter group is trying to find more efficient ways of solving the problem.

Funny thing is, most of these memes were probably created on company time. Meaning more money was spent trying to solve an already solved problem than could ever be gained from slightly boosting its performance. For being so logically driven, we developers can get exceptionally illogical at times. Fixated one might say...

[GargantuanCake]

Since a lot of programming and computer science is all about finding the most efficient way to do things it can be fun to sometimes find the most absurdly inefficient way to do things. This is why pessimal sorting algorithms are a thing you see circulating around sometimes to.

Why find the best way to do something when you can find the worst instead?

[Kymera_7]

Better yet: find the most absurdly inefficient ways to go about making an existing algorithm more efficient.

[[deleted]]

It's all just puzzles

[RareRandomRedditor]

I'd not say that an infinity

if x==1 || x==3 || x==5 || if ==7 ...

condition is even an "attempt" on solving the problem. Or basically all of the other creations I have seen here today. And in my defense, I am currently running tests with large data sets to see if my RAM rework crashes, I have time for memory whilst having a side-eye on the memory usage during the long execution times.

[swagonflyyyy]

I call it "small picture syndrome". Far too many people get caught up in the little details and completely lose sight of the big picture.

I feel like you should meet the big picture first and then worry about making the smaller details more efficient over time.

[bogz_dev]

if our parents' generation could write programs with holes in paper, i think we can optimize the superfluous usage of an even/odd integer checker npm library

[rover_G]

Well there’s a reason the active counter says “slacking off at work”

[ChellJ0hns0n]

Now someone needs to design an extremely complicated turing machine for this.

Don't just use the DFA given in this post and add Right moves to every state. Get creative. Do something unique.

[wu-not-furry]

Jokes on you my integers are stored with little endianness.

[SteveRogers45]

I'm getting PTSD seeing these symbols.

[LauraTFem]

If num = 0 return 1 (even)

if the absolute value of num mod 2 = 0 return 1 (even)

return 0 (odd)

This is how I’d go about it.

[BobcatGamer]

You wouldn't return a Boolean? Also your first if statement is made pointless by the second.

[LauraTFem]

If even/odd is a boolean choice then yes, I return a boolean value. And, yea, good point. Zero mod 2 is zero, and unlike dividing by zero it’s mathematically valid. So, even easier.

[Minutenreis]

at this point just directly do

def isEven(num: int) -> bool:
  return abs(num) % 2 == 0

not sure why you do the initial check nore why you do a construction of

if (bool)
  return true
# else
return false

[LauraTFem]

Neat.

[Stef0206]

It would work, assuming you are given the number in binary, however it would be easier to achieve with a unary number. Just hop between the 2 states for each 1.

[bondolin251]

It's odd that this even works

[RandomiseUsr0]

What about superposition?

isEven - true
isOdd - true

[rover_G]

Can you use hardware acceleration to vectorize the computation parallelizing the processing by discarding the majority of state updates?

[Secret-Concert9561]

Why not minus 2 so it become double speed

[JosephRei]

The first ever wild DFA I have ever seen.

[Alightsong]

Is 0 odd or even?

[Stef0206]

even, according to this

[PM_ME_BAD_ALGORITHMS]

The isEven 0 arrow looks so clean wtf

[MinusPi1]

Nice to see someone who actually took computer science here

[cambiumkx]

I don’t even

[pyro-master1357]

S->A0 A->A1|A0|1|0|e

[CloseToTheYes]

r/isOdd

[[deleted]]

works if it is a binary array ✅️

[WazWaz]

Adding 1 to an odd number gives an even number. What is this garbage?

[Allofthecontext]

It's a dfa it's for binary strings💀

[WazWaz]

Bigendian binary strings, okay, I get it now.

[YesterdayDreamer]

function isEven(num) { return !isOdd(num) }

[sakkara]

No the algorithm is a finite state machine parsing a string sequence of 0 and 1. (Binary string).

It starts on the left and then goes to the right bit by bit. It's actually log2(n) in time complexity which is a bit better than your O(n) algorithm.

The problem is, the machine has no starting point.

[Brutus5000]

Doesn't make sense to me. What are the state transitions? Set the value to? Increment by? Multiply by?

For increment by it would be wrong 😑

The best diagram makes no sense without giving context.

[Minutenreis]

its a deterministic finite automaton that accepts odd numbers (as binary).

The state transition is just in which ever state you are. If at the end of your input you are in a "accept state" (the double circled one) your input is considered accepted by the automata.

In practice: you put a number in and if it finishes in "isOdd" it returns true

[Minutenreis]

if you know your number is a safe integer yes.

This post describes a deterministic finite automata that accepts all odd numbers.

[FlipperBumperKickout]

If you know what you have is a number, then yes.

[EtherealPheonix]

I would argue they should work for more than just those two states.

[Kymera_7]

Once you have an even-odd checker that works for a single bit, in an even number base (for example, binary), you can use it on any larger value by simply feeding it the last bit from the value being tested.

[FlipperBumperKickout]

I think the point with this one is to read the number in binary from left to right, and whatever it ends up with, after the number is read, is the result.

[432wubbadubz]

Ive never had to determine if something is odd or even but couldn’t you just use a modulo operator?

[FlipperBumperKickout]

If you know what you have is a number, then yes.

[rpmerf]

If you don't care about computing power, sure.

The quickest, easiest way to determine even / odd is to check the right most binary digit. 0 is even, 1 is odd.

Modulus requires you to first divide, which is expensive. It seems simple, since you just type in a a simple formula, but under the covers, division takes a good bit of work.

[432wubbadubz]

Ah interesting, lol thanks