post  How to test primality in O(1)

helios (4652)Link to this post
This is "programming meets theoretical physics":
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
bool isprime(ulong n){
    channel c;
    ulong n2=sqrt(n),
        a;
    if (!receive(c,a))
        sendBack(c,2);
    else{
        if (a>n2)
            return 1;
        if (!(n%a))
            return 0;
        sendBack(c,a+1);
    }
    return 0;
}

Depending on the nature of the universe, this is either a deterministic test or a probabilistic test that gives false negatives.
Duoas (2955)Link to this post
Except that sqrt() isn't O(1)...

Of course, I've almost got my lightsaber working... I just need to finish putting up a few more lightning rods to get enough power for the first test.

;-]
helios (4652)Link to this post
Well, we can always make n2=n-1. That's not a problem.

Earlier today, I was talking with a friend about the possibility of writing a language that could simulate this. It would work by running virtual "threads" (it's kind of a misnomer since they wouldn't run concurrently) which would be forked (that is, paused, duplicated, and resumed) or rejoined (stopped and destroyed) accordingly when there were calls to the API functions. In other words, it creates parallel universes to run programs.
I find it too tempting not to try.
Last edited on
tition (236)Link to this post
I think current primality tests do run in parallel
firedraco (1967)Link to this post
Don't think they run in parallel *universes* though...go go quantum computers!
computerquip (542)Link to this post
*Fetches Chubaka costume*
What is the point of this thread again?

This topic is archived - New replies not allowed.