Re: [ID 20010309.004] my-variables lose values while goto'ing withina for(;;)-loop

On Mon, 12 Mar 2001 at 18:24:53, Jarkko laid this on us:

> sub findgteprime { # find the smallest prime integer greater than or equal to
>     use integer;
> 
> # It may be sufficient (and more efficient, IF IT IS CORRECT) to use
> # $max = 1 + int sqrt $num and calculate it once only, but is it correct?
> 
>     my $num = ceil(shift);
>     return 2 if $num <= 2;
> 
>     $num++ unless $num % 2;
> 
>   NUM:
>     for (;; $num += 2) {
> 	my $max = int sqrt $num;
> 	    for ($i = 3; $i <= $max; $i += 2) {
> 		next NUM unless $num % $i;
> 	    }
> 	    return $num;
> 	}
>     }

A bit off the real topic, for which I apologize, but, according to

 http://www-groups.dcs.st-andrews.ac.uk/~history/HistTopics/Prime_numbers.html

the following is an unsolved problem:

4.  Is there always a prime between n ** 2 and (n + 1) ** 2 ?
     (The fact that there is always a prime between n and 2n was called
     Bertrand's conjecture and was proved by Chebyshev.)

If n in the unsolved problem is int sqrt $num, then the algorithm
works iff there *is* a prime between n ** 2 and (n + 1) ** 2,
solving the problem.  My gambling side would favor the existence
of such a prime, but I don't like to gamble with code.

findgteprime3  benchmarks as well as the uncertain algorithm
(findgteprime1) (at least on my Intel PC and an SGI box), 
and doesn't rely on the status of unsolved problems.
But there isn't a *lot* of difference in the runtime of any
of the algorithms.  -- jpl

=======

use Benchmark;

# using POSIX::ceil() would be too heavy, and not all platforms have it.
sub ceil {
    my $num = shift;
    $num = int($num + 1) unless $num == int $num;
    return $num;
}

sub findgteprime1 { # find the smallest prime integer greater than or equal to
    use integer;

# It may be sufficient (and more efficient, IF IT IS CORRECT) to use
# $max = 1 + int sqrt $num and calculate it once only, but is it correct?

    my $num = ceil(shift);
    return 2 if $num <= 2;

    $num++ unless $num % 2;
    my $max = 1 + int sqrt $num;
    my $i;

  NUM:
    for (;; $num += 2) {
        for ($i = 3; $i <= $max; $i += 2) {
            next NUM unless $num % $i;
        }
        return $num;
    }
}

sub findgteprime2 { # find the smallest prime integer greater than or equal to
    use integer;

# It may be sufficient (and more efficient, IF IT IS CORRECT) to use
# $max = 1 + int sqrt $num and calculate it once only, but is it correct?

    my $num = ceil(shift);
    return 2 if $num <= 2;

    $num++ unless $num % 2;
    my $i;

  NUM:
    for (;; $num += 2) {
        my $max = int sqrt $num;
        for ($i = 3; $i <= $max; $i += 2) {
            next NUM unless $num % $i;
        }
        return $num;
    }
}

sub findgteprime3 { # find the smallest prime integer greater than or equal to
    use integer;

    my $num = ceil(shift);
    return 2 if $num <= 2;

    $num++ unless $num % 2;
    my $i;
    my $sqrtnum = int sqrt $num;
    my $sqrtnumsquared = $sqrtnum * $sqrtnum;

  NUM:
    for (;; $num += 2) {
	if ($sqrtnumsquared < $num) {
	    $sqrtnum++;
	    $sqrtnumsquared = $sqrtnum * $sqrtnum;
	}
        for ($i = 3; $i <= $sqrtnum; $i += 2) {
            next NUM unless $num % $i;
        }
        return $num;
    }
}


$n = 500000;
$t = $i = 0; timethis($n, '$t += findgteprime1($i); $i++'); print("\$t = $t\n");
$t = $i = 0; timethis($n, '$t += findgteprime2($i); $i++'); print("\$t = $t\n");
$t = $i = 0; timethis($n, '$t += findgteprime3($i); $i++'); print("\$t = $t\n");

==============

Intel results:

timethis 500000: 565 wallclock secs (258.29 usr +  1.15 sys = 259.44 CPU) @ 1927.23/s (n=500000)
$t = 125004425341
timethis 500000: 608 wallclock secs (277.77 usr +  1.38 sys = 279.15 CPU) @ 1791.15/s (n=500000)
$t = 125004425341
timethis 500000: 534 wallclock secs (256.53 usr +  0.70 sys = 257.23 CPU) @ 1943.79/s (n=500000)
$t = 125004425341

SGI results:

timethis 500000: 630 wallclock secs (626.84 usr +  0.40 sys = 627.24 CPU) @ 797.14/s (n=500000)
$t = 125004425341
timethis 500000: 629 wallclock secs (627.30 usr +  0.40 sys = 627.70 CPU) @ 796.56/s (n=500000)
$t = 125004425341
timethis 500000: 627 wallclock secs (624.89 usr +  0.41 sys = 625.30 CPU) @ 799.62/s (n=500000)
$t = 125004425341

• Re: [ID 20010309.004] my-variables lose values while goto'ing withina for(;;)-loop by John P. Linderman
• Re: [ID 20010309.004] my-variables lose values while goto'ing within a for(;;)-loop by Jarkko Hietaniemi