in reply to A mod2 Machine.

I have to disagree with you conclusions, you're just not comparing like with like.

Which technique is faster depends entirely on the data format. If the data is in binary then you will only have to test the least significant bit, and one bit test will be faster than comparing the last digit against a list of alternatives.

OTOH converting text to binary then performing a mathematical operation may be slower than just operating on the text directly. But you will have to identify the last digit in the text and so will probable be running a regex, which are complex and therefore take time.

So exactly which approach is faster will depend on many factors and will take comprehensive testing to determine which is best.

Modern processors are highly complex and highly optimised and just assuming that mathematical operations are slow is a mistake. You really have to carefully test your code to determine which approach is better in any particular situation. And even they you've only optimised it for one platform if you want your code to portable then that's even more difficult.

In general it's much better to design a simple algorithm that's easy for a human to understand and let the interpreter/compiler & processor work out the best way to run it. Compilers and processors have lots of very clever optimization techniques and they are usually better at turning source code into running code that we are, so let them do their job.

The conclusions you should draw are

  1. It's better to choose an algorithm that matches the data format.
  2. choosing the wrong algorithm could be slow.
  3. Don't second guess the processor/compiler -- test it properly.
  4. designing good tests is hard.

Replies are listed 'Best First'.
Re^2: A mod2 Machine.
by code-ninja (Scribe) on Jul 04, 2013 at 13:46 UTC
    If the data is in binary, the data will be even if its LSB is 0. The mod2 logic does exactly that. For data in the binary format, it is checking the LSB instead of converting the number to decimal or doing other exotic things. You're right about one bit test but then I'm using the mod2 logic to handle all kinds of numbers (where all kinds == {decimal, octal, hexadecimal, binary}).

    my $n = 534587; print "even\n" if($n % 2 == 0);

    This will print nothing on the screen (obviously, it indicates that the number is odd) and no matter how fast the processor is, the condition inside "if" will actually be evaluated i.e. 534587 will actually be divided by 2 and the remainder will be compared with 0. Do any compiler/processor optimization, this fact will not change (afaik, that is to say).


    my $n = "534587"; print "even\n" if ($n =~ /[02468]$/);

    there are no mathematical evaluations here, no matter how big the string is, the regex here just checks last character. There will be no need of actually calculating the remainder and comparing.

    I'm not saying that processor will take time to evaluate a mathematical expression, it will be derogatory to think that about modern processors. I'm just trying to stress on the fact mod2 machine circumvents any mathematical operation.

    This algorithm does fail if the bases are not of the form of 2^n or base 10. Also, as ww said, it will fail for base 3 numbers on a quantum computer