-----------------------------------

iamcow

Thu Aug 03, 2006 1:02 pm


computation speed

-----------------------------------

just something i did while fooling around with a piece of code


var primes : array 2 .. 99999999 of boolean

proc findprime (num : int)
    var counter := 0
    var n : real
    for decreasing i : num-1 .. 2
        n := num / i
        if round (n) = n then
            counter += 1
        else
            counter := counter
        end if
    end for
    if counter = 0 then
        primes (num) := true
    else
        primes (num) := false
    end if
end findprime

for i : 2 .. 99999999
    findprime (i)
end for

for i : 2 .. 99999999
    if primes (i) = true then
        put i, " is a prime"
    else
        put i, " is not a prime"
    end if

end for


out of curiousity, how long does it take for you guys to run this program?


-----------------------------------

[Gandalf]

Thu Aug 03, 2006 1:19 pm



-----------------------------------

Umm...  I'd imagine extremely long, even on an amazing computer.  Why do you ask?

And just from a glance, you're findPrime function doesn't look quite right, and neither does your code.


-----------------------------------

pj_ladd12

Thu Aug 03, 2006 1:31 pm



-----------------------------------

yeah...nothing came up lol


-----------------------------------

BenLi

Thu Aug 03, 2006 4:39 pm



-----------------------------------

changed all  "99999999"'s to 100s
the code works actually, i imagine its just quite slow.

Interesting, this is the subject of another discussion in general forum. The one about largest primes?


-----------------------------------

[Gandalf]

Thu Aug 03, 2006 11:31 pm



-----------------------------------

yeah...nothing came up lol
Yeah, that's because it's taking a very long time to calculate what it's going to display.

Interesting, this is the subject of another discussion in general forum. The one about largest primes?
I doubt you'd get very far using this algorithm and Turing.


-----------------------------------

Clayton

Fri Aug 04, 2006 9:03 am



-----------------------------------

I'm sure theres a much better way to do this, it just had to be extremely well organized and optimized :D, the only problem is, Turing can't deal with big enough numbers to find the worlds next largest prime with over 10,000,000 digits


-----------------------------------

MysticVegeta

Fri Aug 04, 2006 10:51 am



-----------------------------------

Why not just try the Sieve of Eratosthenes to find it quicker than that algorithm but still it takes time to find that many...

http://compsci.ca/v2/viewtopic.php?t=11966


-----------------------------------

CodeMonkey2000

Sun Aug 06, 2006 9:43 pm



-----------------------------------

var primes : array 2 .. 99999999 of boolean


wow soo much time was spent on just declareing the all elements of primes.
turing really isnt that powerful.


-----------------------------------

Andy

Wed Aug 09, 2006 2:15 am



-----------------------------------

var primes : array 2 .. 99999999 of boolean


wow soo much time was spent on just declareing the all elements of primes.
turing really isnt that powerful.

what? you clearly have no knowledge of the computer memory interface. when declaring 99999998 boolean variables, 99999998bytes of contiguous memory (either on RAM, or on disk through an TLB) is allocated, it's all done by the processor, and has nothing to do with turing's efficiency