how to calculate euler phi function of integer from 1 to n effectively?

[bytebites]

After deleting assignment Node:=G, program obviously gets into infinite loop. M does not change.

[rabbit_dance]

thanks, i will check later.

[rabbit_dance]

what's your problem?

My problem (as explained to you in another thread) is, that it is hard to read text (code) that is in all capitals.
Reading to me (and probably most western-european etc.) comes more natural if written "natural" (for lack of a better word): use capitals where you would use it when you would write a normal sentence.
For programming languages like Pascal (that do not make a distinction between upper- and lowercase) uppercasing can be used to emphasize or to make better reading of certain words e.g.

Code: [Select]

procedure CalculateEvenCatalanNumbers;  //this way of using capitals is called CamelCase
vs
procedure calculateevencatalannumbers; 
vs
procedure CALCULATEEVENCATALANNUMBERS;

For me the first one makes it obvious in one glance what the procedure is meant to do.

Proper indentation (use the same style of indentation everywhere) and separation of procedures/functions also helps.

Code: [Select]

PROCEDURE PRINTING(PTR:LINKED_PTR);
VAR P:LINKED_PTR;
BEGIN
P:=PTR;
P:=P^.NEXT;
R:=R+1;
WRITE('  ',R,' ',P^.VALUE);
IF P^.NEXT=NIL THEN EXIT();
PRINTING(P);
FREEMEM(P,SIZEOF(LINKED_PTR));
END;
PROCEDURE SUCCESSOR(VAR PTR:LINKED_PTR);
VAR P:LINKED_PTR;
BEGIN
    IF PTR^.NEXT=NIL THEN BEGIN
        (*CREATE A NEW NODE AND LINK IT TO PREVIOUS ONE*)
        PTR^.NEXT:=ALLOCMEM(SIZEOF(LINK_NODE));
        P:=PTR^.NEXT;PTR:=P;
END;
END;

Versus

Code: [Select]

procedure Printing(Ptr: Linked_Ptr);
var
  P:Linked_Ptr;
begin
  P:=Ptr;
  P:=P^.Next;
  R:=R+1;
  Write('  ',R,' ',P^.Value);
  IF P^.Next=nil then Exit();
  Printing(P);
  FreeMem(P,SizeOf(Linked_Ptr));
end;

procedure Successor(var Ptr:Linked_Ptr);
var
  P:Linked_Ptr;
begin
  if Ptr^.Next=nil then
  begin
    (*Create a new node and link it to previous one*)
    Ptr^.Next:=AllocMeM(SiseOf(Link_Node));
  end;
  P:=Ptr^.Next;
  Ptr:=P;
end;

It's so much less strain on the eyes.

Bart

how do you change my text into the text you have shown.

[Bart]

how do you change my text into the text you have shown.

I did it by hand.
Many editors have a function to change text to lowercase (with or without laving the starting capital of each word/sentence untoched), so that would be a starting point if you wanted to automate it.
The Lazarus IDE has such a feature (lowercase/uppercase/swap case).

Best way of course is to type it like that from the beginning.

Bart

[rabbit_dance]

Code: [Select]

PROGRAM EULER_PHI;
TYPE LINKED_PTR=^LINK_NODE;
        LINK_NODE=RECORD
        VALUE:INTEGER;
        NEXT:LINKED_PTR;
END;
VAR N,M,I,R:INTEGER;VAR NODE,G:LINKED_PTR;
PROCEDURE PRINTING(PTR:LINKED_PTR);
VAR P:LINKED_PTR;
BEGIN
P:=PTR;
P:=P^.NEXT;
R:=R+1;
WRITE('  ',R,' ',P^.VALUE);
IF P^.NEXT=NIL THEN EXIT();
PRINTING(P);
FREEMEM(P,SIZEOF(LINKED_PTR));
END;
PROCEDURE SUCCESSOR(VAR PTR:LINKED_PTR);
VAR P:LINKED_PTR;
BEGIN
    IF PTR^.NEXT=NIL THEN BEGIN
        (*CREATE A NEW NODE AND LINK IT TO PREVIOUS ONE*)
        PTR^.NEXT:=ALLOCMEM(SIZEOF(LINK_NODE));
END;
        P:=PTR^.NEXT;PTR:=P;
END;
PROCEDURE ASSIGNMENT(PTR:LINKED_PTR;N:INTEGER);
VAR K:INTEGER;
BEGIN
        FOR K:=1 TO N DO
        BEGIN
                SUCCESSOR(PTR);
        END;
END;
PROCEDURE TRAVERSE_ELEMENTS(O:LINKED_PTR; VAR Q:LINKED_PTR;K:INTEGER);
VAR T:INTEGER;
BEGIN
    FOR T:=1 TO K DO
    BEGIN
        SUCCESSOR(O);
    END;
    Q:=O;
END;
BEGIN
R:=1;
READLN(N);
NODE:=ALLOCMEM(SIZEOF(LINK_NODE));
NODE^.VALUE:=1;
ASSIGNMENT(NODE,N);
M:=2;
WHILE(M<=N) DO
BEGIN
        TRAVERSE_ELEMENTS(NODE,G,M);
        IF G^.VALUE=0 THEN BEGIN
            I:=M;
            WHILE(I<=N) DO
            BEGIN
                TRAVERSE_ELEMENTS(NODE,G,I);
                IF G^.VALUE=0 THEN G^.VALUE:=I;
                G^.VALUE:=(G^.VALUE DIV M)*(M-1);
                I:=I+M;
            END;
            END;
            M:=M+1;
END;
PRINTING(NODE);
READLN();
END.

please run it.

[Bart]

Crash!

Code: [Select]

C:\Users\Bart\LazarusProjecten\ConsoleProjecten\bugs\euler>euler
10
  2 0  3 1  4 2  5 2  6 4  7 2  8 6  9 4  10 6  11 4Marked memory at $001A5C20 i
nvalid
Wrong size : 8 allocated 4 freed
  $00409EB9
  $00404C86
  $004014EC  PRINTING,  line 16 of euler.lpr
  $004014EC  PRINTING,  line 16 of euler.lpr
  $004014EC  PRINTING,  line 16 of euler.lpr
  $004014EC  PRINTING,  line 16 of euler.lpr
  $004014EC  PRINTING,  line 16 of euler.lpr
  $004014EC  PRINTING,  line 16 of euler.lpr
  $004014EC  PRINTING,  line 16 of euler.lpr
Call trace for block $001A5C20 size 8
  $00401570  ASSIGNMENT,  line 33 of euler.lpr
  $00401621  main,  line 50 of euler.lpr
Heap dump by heaptrc unit
13 memory blocks allocated : 307/320
2 memory blocks freed     : 223/240
11 unfreed memory blocks : 84
True heap size : 131072 (128 used in System startup)
True free heap : 130064
Should be : 130160
Call trace for block $001A5C70 size 8
  $00401570  ASSIGNMENT,  line 33 of euler.lpr
  $00401621  main,  line 50 of euler.lpr
Call trace for block $001A5C20 size 8
  $00401570  ASSIGNMENT,  line 33 of euler.lpr
  $00401621  main,  line 50 of euler.lpr
Call trace for block $001A5BD0 size 8
  $00401570  ASSIGNMENT,  line 33 of euler.lpr
  $00401621  main,  line 50 of euler.lpr
Call trace for block $001A5B80 size 8
  $00401570  ASSIGNMENT,  line 33 of euler.lpr
  $00401621  main,  line 50 of euler.lpr
Call trace for block $001A5B30 size 8
  $00401570  ASSIGNMENT,  line 33 of euler.lpr
  $00401621  main,  line 50 of euler.lpr
Call trace for block $001A5AE0 size 8
  $00401570  ASSIGNMENT,  line 33 of euler.lpr
  $00401621  main,  line 50 of euler.lpr
Call trace for block $001A5A90 size 8
  $00401570  ASSIGNMENT,  line 33 of euler.lpr
  $00401621  main,  line 50 of euler.lpr
Call trace for block $001A5A40 size 8
  $00401570  ASSIGNMENT,  line 33 of euler.lpr
  $00401621  main,  line 50 of euler.lpr
Call trace for block $001A59F0 size 8
  $00401570  ASSIGNMENT,  line 33 of euler.lpr
  $00401621  main,  line 50 of euler.lpr
Call trace for block $001A59A0 size 8
  $00401570  ASSIGNMENT,  line 33 of euler.lpr
  $00401621  main,  line 50 of euler.lpr
Call trace for block $001A5950 size 8

Bart

[rabbit_dance]

wu@localhost ~ $ ./euler_phi
19
  2 1  3 2  4 2  5 4  6 2  7 6  8 4  9 6  10 4  11 10  12 4  13 12  14 6  15 8  16 8  17 16  18 6  19 18

[Bart]

Well, it's your code.
I just pasted it and compiled with fpc 3.0.0rc1 on Windows.

Bart

[rabbit_dance]

i want to know what occurs that effect happened, too.

[rabbit_dance]

Well, it's your code.
I just pasted it and compiled with fpc 3.0.0rc1 on Windows.

Bart

are you german?

[Bart]

There's another way to calculate Phi: https://en.wikipedia.org/wiki/Euler's_totient_function#Computing_Euler.27s_totient_function
But I haven't tested its efficiency, it might be even less efficient (for N<1000000) due to multiple calculation of prime numbers. And definitely the complex code would need a lot of debugging.

It would also give rounding errors:
93296 consists of the following primes: 1, 2, 7, 17
The Result would be 93296 * (1-1/2) * (1-1/7) * (1-1/17) = 37632, but calculating this with floating point numbers will give a wrong result.
Calculating it using Fractions (using integer multipliction, greates common divisor etc) may overflow very easily (e.g. when a number has some primes > 1000).

The multiple computing of prime numbers can be overcome by having a static table of primes (up til Sqrt(High(UInt64))?).

It would be nice to build such a thing though.
The fractions part is easy, I already have a fractions unit.

Bart

[Bart]

are you german?

No, I'm not. Why would you think so?
But I fail to see the relevance for this particular problem 

Bart

[rabbit_dance]

Do you want to know about the principle behind the program?

[Bart]

See attached program for my solution for EulerPhi(N)  using factorization and the EulerProduct of (1-1/p) where p is a prime factor of N.

It needs the Fractions unit (see a previous post of mine).

Bart

[BeniBela]

If you want it for all numbers from 1 to n, you need to use a sieve: https://github.com/benibela/bbutils/blob/master/bbutils.pas#L4725-L4777