Re: primality

On 4/3/2007 8:17 PM, Antony Clements wrote:
"Mark Nudelman" <markn@xxxxxxxxxxxxxxxxxxxxx> wrote in message
news:JMidnW0xUP4KZI_bnZ2dnUVZ_vOlnZ2d@xxxxxxxxxxxxxx
On 4/3/2007 5:04 PM, Antony Clements wrote:
If you've got an integer n = 12345, this is represented in most
languages as a 32-bit word with the value
00000000,00000000,00110000,00111001.
Usually programmers would write this as a hex value 0x3039.

Please don't patronize me, i've been programming for 10 + years (16 or so if
you include playing around with BASIC code in my teen years), I rarely see
any number written as hex unless it is larger than 14 or so digits. 12345
written as a binary string is 00110001,00110010,00110011,00110100,00110101.
by taking an integer and placing it in a string each digit is counted as 1
byte. There is no modulo division (that i know of). Either way converting
into a string and testing the last byte in the string, and testing the
integer whether it has 1 3 7 or 9 as the last digit (the former is the
simplest and possibly most efficient way that i know of) has no significant
timing differences.

I'm sorry, I'm not trying to patronize you, but you are sayings things
that indicate to me that you don't really understand what's happening at
a low level, below the level of your high level language. The binary
string you've written is the *ASCII* representation of 12345. This is
NOT how an integer variable is stored internally, except in a very few
languages which deal with numbers internally in ASCII. In any language
in which it would be reasonable to write high performance math
functions, numbers are stored in radix-2, not in ASCII. You don't have
to take my word for it, just disassemble a piece of code and look at it.

I really do know what I'm talking about here, honest. I've been
programming a lot longer than your 16 years, and I've written assembly
language, I've written compilers, I've done OS programming, and my code
is running on millions of Linux systems.


Now if you assign that number to a string variable, the computer needs
to calculate the decimal representation of this value. You can see by
looking at the binary value above and the equivalent hex value that
there's no easy way to get the five digits 12345 out of what is already
known. So it has to calculate the digits. It does this by a loop
similar to this:
while (n > 0) {
digit = n % 10;
store digit into string;
n = n / 10;
}
It's a little more complicated than that, but that's basically the idea.
You can see that this involves five divisions by 10, in the case of
your five digit number. Longer numbers would involve more divisions.

If your language has a debugger that lets you look at the compiled
assembly language, you should be able to see this. You might see a call
to a built-in function that does this rather than seeing the code
inline. But what you certainly won't see is a simple MOV statement that
copies an integer into a string. It's just not possible.

you are correct there, on an ASM level it is not possible. but higher level
functions do not represent single ASM commands, they represent 10's and
possibly thousands in order to achieve the goal of the function. you may be
correct on an ASM level, but I don't know ASM all that well so i can't
comment on that.

Exactly, that's the point. One high level statement like "string = n"
compiles into many assembly language instructions. And a computer
always executes that machine code, not the high level language.

But how it is achieved is rather irrelevant as both methods
have very similar timings.

Yes, a good compiler can produce assembly language that rivals
hand-crafted assembly. But that's not the point -- earlier you seemed
to be saying that the high level language somehow bypassed the need to
execute this assembly code at all. As if "string = n" executed in O(1)
time because it was one statement in the high level language. In fact,
it compiles into an assembly language loop including multiple divisions
as I explained, so it takes quite some time to execute, much longer than
assigning an integer variable to another integer variable.


Now can we get back to comments on the sweeping statement i made which was

"From looking at the sequences it appears that _most_ numbers with the last
digit as a 1 3 7 or 9 will fall into the category of _either chen or cousin
prime_. If you want to weed out the 24.5% or so that don't thats up to you,
but really what is the point since those numbers
will fall into one of the other 70 categories of prime number. If the number
falls into _any_ of the 72 categories of prime, then it is a valid number
and can be used. So literally there is only one test needed and it is very
fast. If you wanted to test for a specific category of prime then there are
other tests that will weed out most numbers not in that category such as the
fermat test and the M-R test."

Um, any number that does not end in 1, 3, 7 or 9 is not prime, period.
There's no deep insight there. Any number that ends in an even digit is
even, and any number that ends in 0 or 5 is divisible by 5. You're just
saying that primality testing should start with testing a few small
prime factors, like 2 and 5. Many prime tests do this, as well as other
small factors like 3 and 7 which aren't amenable to discovery by looking
at the DECIMAL representation of the number. But 2 and 5 aren't special
-- doing any of these tests involves doing a division. There isn't any
shortcut unless the number is already represented as radix-10, which is
usually isn't.

--Mark
.

Relevant Pages

  • Re: "Collatz 3n+1 conjecture is unprovable" paper
    ... there exists a "language" in which it can be ... For a string S, my "language" is... ... the right "language" to collapse the infinite complexity into the ... Your logic essentially says a representation of pi ...
    (sci.math)
  • Re: Parallel Prolog
    ... Parlog, Strand, FGHC (all essentially the same language with very minor ... What they inherited from Prolog was rather limited, ... really a "high level language" at all, ... The silliest thing is that its syntax disguises what is actually fundamental ...
    (comp.lang.prolog)
  • Re: Microcontroller Project
    ... You could write the C program on a PC first, and then port to your ... The advantage of using a high level language like C is that you ... shouldn't have to care what micro platform it is used on. ... surprised your teacher is not forcing you to use assembler language. ...
    (sci.electronics.design)
  • Re: What can C do and Basic V2 not?
    ... C for example is not good for object oriented programming, ... work out why language Z is more useful than language Q for some things. ... Basic is a high level language, C is a lower level one. ... CLC FAQ ...
    (comp.lang.c)
  • Re: Why is C good??? any experts?
    ... Ruby etc.) And IMHO its foolish to compare languages like this to C as ... its because no other language has been able to ... replace it and it still is the choice of programming language. ...
    (comp.lang.c)
Quantcast