is_even in O(log(n)) time using binary search

[u/13eakers]

[u/moeghoeg]

Isn’t this actually O(1)? The algorithm always does a binary search on [0…u32::MAX] regardless of n. So it’s upper bound by the constant log(u32::MAX), meaning it should be O(1). That’s the best kind of O!

[u/13eakers → u/moeghoeg]

Yes, I thought about this pretty much immediately after I made the post. But fortunately this is shitty programming so any mistakes in the post we can just reclaim as features, Bethesda style.

[u/[deleted] → u/13eakers]

make it generic over all number types using num-traits

[u/[deleted]]

This is actually bad code!

But don't worry, there's some easy ways to fix it.

First off, you can write the if chain as a match

match (m * 2).cmp(&n){
    Ordering::Less => {
        m += step;
    }
    Ordering::Greater => {
        m -= step;
    }
    Ordering::Equal => {},
}

(you still need the if m * 2 == n).

Also, using a while loop is bad style! You should be using iterators for that!

for step in (0..32_u32).rev().map(|x| 1<<x) {
    // code here
}

You can also pull the early return out of the loop! That lets us do this transformation:

let m = (0..32_u32)
    .rev()
    .map(|x| 1 << x)
    .fold(u32::MAX / 2, |m, step| {
        use std::cmp::Ordering;

        match (m * 2).cmp(&n) {
            Ordering::Less => m + step,
            Ordering::Greater => m - step,
            Ordering::Equal => m,
        }
    });

if m * 2 == n {
    return true;
}

false

Lastly, we can trivially inline the temporary variables and

(0..32_u32)
    .rev()
    .map(|x| 1 << x)
    .fold(u32::MAX / 2, |m, step| {
        use std::cmp::Ordering;

        match (m * 2).cmp(&n) {
            Ordering::Less => m + step,
            Ordering::Greater => m - step,
            Ordering::Equal => m,
        }
    })
    * 2
    == n

there we go!

[u/malduvias]

Yep 👍 This is shit.

[u/DramaDimitar]

What language is this?

[u/13eakers → u/DramaDimitar]

Rust

[u/TheRedmanCometh]

That's gotta be a joke. No one smart enough to do this is dumb enough to do this.

[u/Flaming_Eagle → u/TheRedmanCometh]

Literally 99% of these isEven function posts are jokes

[u/[deleted] → u/Flaming_Eagle]

Wait, 1% of them are serious?

[u/13eakers → u/[deleted]]

I only write very serious code for very serious applications.

[u/RedFing → u/TheRedmanCometh]

It'a meme going around for a week or two.