Should we compare ?

[JRS]

Nice improvement!

Code: [Select]

#include <math.h>
#include <stdio.h>
#include "cbasic.h"

MAIN
BEGIN_FUNCTION
  DIM AS int i, n, sum;
  DEF_FOR (n = 2 TO n <= 10000 STEP INCR n)
  BEGIN_FOR
    sum = 0;
    DEF_FOR (i = 2 TO i <= sqrt(n) STEP INCR i)
    BEGIN_FOR
      IF (n MOD i EQ 0) THEN_DO sum = sum + i + n / i;
    NEXT
    IF (sum EQ n - 1) THEN_DO PRINT ("%i\n", n);
  NEXT 
  RETURN_FUNCTION(0);
END_FUNCTION

jrs@laptop:~/C_BASIC/bench$ gcc -O3 perfnum.c -l m -o perfnum2
jrs@laptop:~/C_BASIC/bench$ time ./perfnum2
6
28
496
8128

real   0m0.009s
user   0m0.008s
sys   0m0.000s
jrs@laptop:~/C_BASIC/bench$


.

[Charles Pegge]

By precalculating sqrt(j), you should see a further improvement in performance

long k=sqrt(i)
for j=2 to k
...

[JRS]

Strange!

That actually increased the time

Code: [Select]

#include <math.h>
#include <stdio.h>
#include "cbasic.h"

MAIN
BEGIN_FUNCTION
  DIM AS int i, n, s, sum;
  DEF_FOR (n = 2 TO n <= 10000 STEP INCR n)
  BEGIN_FOR
    sum = 0;
    s = sqrt(n);
    DEF_FOR (i = 2 TO i <= s STEP INCR i)
    BEGIN_FOR
      IF (n MOD i EQ 0) THEN_DO sum = sum + i + n / i;
    NEXT
    IF (sum EQ n - 1) THEN_DO PRINT ("%i\n", n);
  NEXT 
  RETURN_FUNCTION(0);
END_FUNCTION

jrs@laptop:~/C_BASIC/bench$ gcc -O3 perfnum.c -l m -o perfnum2
jrs@laptop:~/C_BASIC/bench$ time ./perfnum2
6
28
496
8128

real   0m0.012s
user   0m0.008s
sys   0m0.000s
jrs@laptop:~/C_BASIC/bench$

[Charles Pegge]

C might already be optimising sqrt() to a variable

[RobbeK]

   Cool

A little competiion always enhances productivity ..

I had an idea about memoization , but I need pen and paper to work out something ...

28 -> 14 , 7 , 4 , 2 , 1
14 -> 7 , 2 , 1   :::   memo(14)=10

28 -> 14+memo(14)....   +4    ..  nope, nothing , can be done with n! etc ..  , not here ...

thanks for the file , John
Charles :  what makes the difference between     k=sqrt(x)     ...  to sqrt(x) ?  /  floating point - integer compare  every next cycle ?
it indeed runs faster 32mSec vs 46 mSec..



best Rob     

[Charles Pegge]

The end comparator is currently translated literally in Oxygen and square roots are expensive!

I am considering whether to change this interpretation and assign the end value expression to a temp variable before entering the iteration.

[RobbeK]

Ah, thanks Charles  ..  I see 

In Forth (but it's more than 30 yrs ago)  there was something as

...   [ 5 SQR ] LITERAL  ....    where [..] was calculated by the interpreter and the value entered into the code by the compiler.
(but then you need a kind of interpreter -- ? )   ..  in interpreted mode, the interpreter just ran over the brackets and the LITERAL word , I think ..

best Rob
(thinking about it,  with tB there's an interpreter at hand ...  maybe with a kind of EXPAND function tB can replace "literals" by number values ? )

[RobbeK]

....  the final .....

Reaching the 5th number took around 50 minutes with this method.
Trying patern matching :
The divisors have a more or less similar behaviour --  powers of 2 with one "crack" in it then the 2x goes on ,  like
1 2 4 7(the crack) 14 28 .
It's easier to see when writing the PNumbers binary     1......10.....0   (exclusive 1 of a certain size & then exclusive 0 of a certain size )
Using such a generator , gave attached result ; but
- it of course generates a very lot of numbers that are not perfect / needs the usual filtering
- I can not prove it will generate all P numbers

Anyway the 5th number after 1/4 sec ...
soon outside the range of uint32 anyway ... (in this case I can switch to CLisp).

best Rob


.

[Charles Pegge]

Hi Rob, you can use quads instead of ints. It might give you the next number ..

[RobbeK]

Hi Charles,

I'll have a look if I can use the FBmath  (Jean Debord) lib from freebasic in Oxygen (i only have the .inc and .a files iirc ) -- it has large integers.
I cheated a little and used the Mersenne numbers to generate the Perf's    (in Scheme : a daughter of mother Lisp ).
From (other) tests I think it is about 4x slower than O2 .. (which I still consider fast )

best Rob
-- the binary pattern is remarkable ...

.

[Charles Pegge]

Wow! That's interesting. I wonder I you can predict perfect numbers, based on their bit pattern. Could there be a proof?

[RobbeK]

Hi Charles,

Yes, I do think all even perf N can be found this way - proving it, is something else.

I started now to write the code without the help of the Racket Scheme Number theory module. 
Still based on Mersenne numbers, i do have to check the primality of these for generating perfect numbers.
I use Miller Rabin , a Monte Carlo method ( the classic (and naive) try every number below the sqrt and if nothing divides it's a prime, may take hours, days with these huge numbers ).
While with this method some pseudo primes may enter the system, we're extremely lucky here, because the divisors can be build in no time from the binary pattern  (just sum them, and check against the number )

Common Lisp for the moment, but when I find a suitable big / large number lib for oxygen , it will be ported ..

best Rob (have a look at the time needed to find these numbers ...    )



.

[JRS]

Common Lisp for the moment, but when I find a suitable big / large number lib for oxygen , it will be ported ..

Are you compiling as 32 bit or 64 bit under O2?

All my C BASIC examples are 64 bit gcc.

[Charles Pegge]

Some of these numbers could be 64 million bits wide You have to crunch them using techniques similar to the manual methods we learnt during our school days, before calculators.

There is an example: examples/math/BCDmul.o2bas. It is mostly assembly code, which I might be able to improve with a little more Basic.

[RobbeK]

Hi Charles, John ,

32bit here --

Yep, back to the 70s  --  we did it all with 8bit numbers, not ?  With Clisp the fun is over soon and  runs out of (soft) 2048 (?) bit integers "soon" - (attached.) But it has modulo math operators built in (iirc).  I think Racket and NewLisp have unlimited (limited by available memory ) numbers.  But once again the operations are very simple , if extended this method , the Miller Rabin does not use a squareroot and the core of program (see attached too) is based on powers of 2 , which is just a binary shift of the blocks to the left with one carry / block. The perfect function gives either 0 or a perfect number.  I did not test the results here - the Miller Rabin goes 8 deep - but there's still a chance a "deep-liar" surfaces (less chance than winning the lottery tomorrow ...  but to be exact it needs verification).
For this reason I'll try the pattern matching algorithm which easily generates the divisors and a proof.

best Rob

.