Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Test if a number is even

ubuntuincident.wordpress.com

Post reply on HN
Print view View original

31–40 of 68 posts

Re: Test if a number is even

#31

Post by matt_daemon »

dietr1ch wrote: post #16
tux3 wrote: post #6

Optimizing compilers have been able to recognize pretty complicated patterns for many years. For instance if you're making a loop to count the bits that are set in a number, the compiler can recognize the entire loop and turn it into a single popcnt instruction (e.g. https://lemire.me/blog/2016/05/23/the-surprising-cleverness-... )

I feel that the compiler is doing too much work here. I know they are thinking about special cases on generated code, but at some point it feels that it just adds compile time for no good reason. Look at this --beauty-- eww, thing, should compilers really spend time trying to figure out how to optimise insane code? def is_even(n): return str(n)[len(str(n))-1] in [str(2*n) for n in range(5)]

Or even:

    def is_even(n):
        return str(n)[-1] in "02468"

Re: Test if a number is even

#33

Post by dietr1ch »

refulgentis wrote: post #23
dietr1ch wrote: post #16

Earlier quoted context omitted.

I feel that the compiler is doing too much work here. I know they are thinking about special cases on generated code, but at some point it feels that it just adds compile time for no good reason. Look at this --beauty-- eww, thing, should compilers really spend time trying to figure out how to optimise insane code? def is_even(n): return str(n)[len(str(n))-1] in [str(2*n) for n in range(5)]

Maybe one day there will be compilers that can choose what to optimize based on their aesthetic judgement of the code. I could see that as a novel feedback mechanism for software engineers. As it stands, I'm glad they design optimizations abstractly, even if that means code I don't like gets the benefits

It's not about aesthetics, but about the sort of hit-rate of the optimisations as if they need to be too smart to figure things out, then it also means that they'd more rarely be used and necessary.

Re: Test if a number is even

#34

Post by plagiarist »

crazydoggers wrote: post #17
the_real_cher wrote: post #3

I like the algorithms that are the opposite of this where they try to find the slowest possible way to determine if a number is even.

There’s no upper limit, so there’d have to be some set of rules like no sleep(n). Also given the halting problem, you could write an algorithm that would be impossible to determine if it loops forever.

If the results of TREE(n) had specific properties for even n, you could easily check by first calculating TREE(n) and then looking for those properties in the results. Might need a bignum library.

Re: Test if a number is even

#35

Post by deathanatos »

In Javascript, NaN (not a number) is a number:

  >> typeof NaN
Let's see then:

  >> (NaN % 2) == 0
So clearly NaN is odd. /s

(And if you're thinking "you gotta equals harder":

  >> (NaN % 2) === 0
Nope, still odd.

Both of the infinities are also odd by the same logic, too, if you were curious.

null and false are even. true is odd. [] is even, [0] is even, [1] is odd.)

Re: Test if a number is even

#36

Post by userbinator »

I'm nowhere near an APL-level programmer, but that C example already looks ridiculously verbose to me; the body of the loop could be simply written branchlessly as:

    total += !(i&1);
...and since there's another comment here about Asm, I'd compile the above as (assume edx is i and total in eax, high 24 bits of ebx precleared):

    test dl, 1
    setnz bl
    add eax, ebx

Re: Test if a number is even

#37

Post by userbinator »

dansalvato wrote: post #30

The interesting thing about testing values (like testing whether a number is even) is that at the assembly level, the CPU sets flags when the arithmetic happens, rather than needing a separate "compare" instruction. gcc likes to use `and edi,1` (logical AND between 32-bit edi register and 1). Meanwhile, clang uses `test dil,1` which is similar, except the result isn't stored back in the register, which isn't relevant…

That instruction only encodes to 2 bytes, so size-wise it's the most efficient.

In isolation it's the smallest, but it's no longer the smallest if you consider that the value, which in this example is the loop counter, needs to be preserved, meaning you'll need at least 2 bytes for another mov to make a copy. With test, the value doesn't get modified.

Re: Test if a number is even

#39

Post by amiga386 »

dansalvato wrote: post #30

The interesting thing about testing values (like testing whether a number is even) is that at the assembly level, the CPU sets flags when the arithmetic happens, rather than needing a separate "compare" instruction. gcc likes to use `and edi,1` (logical AND between 32-bit edi register and 1). Meanwhile, clang uses `test dil,1` which is similar, except the result isn't stored back in the register, which isn't relevant…

> On m68k, shifting right by 1 and performing a logical AND both take 8 CPU cycles. But the right-shift is 2 bytes smaller

There's also BTST #0,xx but it wastefully needs an extra 16 bits say which bit to test (even though the bit can only be from 0-31)

> That makes a difference on Amiga, because (other than size) the DMA might be shared with other chips, so you're saving yourself a memory read that could stall the CPU while it's waiting its turn.

That's a load-bearing "could". If the 68000 has to read/write chip RAM, it gets the even cycles while the custom chips get odd cycles, so it doesn't even notice (unless you're doing something that steals even cycles from the CPU, e.g. the blitter is active and you set BLTPRI, or you have 5+ bitplanes in lowres or 3+ bitplanes in highres)

Re: Test if a number is even

#40

Post by MathMonkeyMan »

TZubiri wrote: post #19
mtmail wrote: post #7

Earlier quoted context omitted.

https://github.com/blackburn32/serverlessIsEven "A serverless implementation of isEven. Now you can know if your numbers are even, even at mass scale."

How about sending a packet back and forth to a server in another continent n times, and if it stops coming back, it was odd.

Better to use TCP, but I like your approach.
Post reply on HN