Wednesday, February 12, 2020

Calculating prime numbers in RPG

calculating prime numbers in rpg

The germ for this post is from a question that was asked in an interview. This person, a self confessed RPG "fresher", had been asked to write a "RPG free" program to calculate the prime numbers between 1 and 11. This request intrigued me, and made me think what kind of program the interviewer probably wanted, and what I would write if I need to use this at work.

Let me start with the basics, the definition of what is a prime number:

Any integer other than 0 or 1 that is not divisible without remainder by any other integers except 1 and the integer itself

Taken from the Merriam Webster dictionary.

What are the prime numbers in the desired range:

2, 3, 5, 7, 11

First let me show the program I would have written if I had been in this interview.

01  **free
02  dcl-c MaxRange const(11) ;
03  dcl-s Number packed(3) ;
04  dcl-s Divisor like(Number) ;
05  dcl-s Text char(20) ;

06  for Number = 2 to MaxRange ;
07    Text = ' ' ;                             

08    for Divisor = 2 to (Number - 1) ;
09      if (%rem(Number:Divisor) = 0) ;
10        Text = %char(Number) + ' not prime' ;
11        leave ;
12      endif ;
13    endfor ;

14    if (Text = ' ') ;
15        Text = %char(Number) + ' is prime' ; 
16    endif ;

17    dsply Text ;
18  endfor ;

19  *inlr = *on ;

Line 1: They wanted a "RPG free" program so this is going to be one.

Line 2: This is the free format definition for a constant. I am using this constant as the maximum number I will check if it is a prime number. The request was for 1 – 11, therefore, this constant contains the value of 11. I made this a constant as if I need to change the maximum number in the range then I could just change this.

Lines 3 – 5: Definitions of the variables I will be using.

Line 6: I always prefer to use a FOR group when I need to loop and increment values. In this example I am initializing the variable Number with 2, as I have not given a value to increment 1 is assumed, to the value of the constant MaxRange which is 11.

Line 8: A second FOR group. This time it is the Divisor, the number the variable Number is divide by, that is being incremented. It is initialized with 2, incrementing is assumed as 1, to the value of Number minus 1. Why to Number - 1? I don't need to perform the calculation of dividing the number by itself, therefore, I want to stop looping before I get to the value of Number.

Line 9: What I love about Built in Functions is that I can use them in a IF statement. In this case I am using the %REM built in function and if the remainder returned is zero then the Number tested is not a prime, and Text is updated with a string to say that the tested number is not a prime.

Line 14: By the time the logic reaches here either the number tested is not a prime, Text is not blank, or the program has performed the check of remainder with every necessary divisor, Text is blank so the number must be a prime.

Line 17: I display the string in Text.

Line 18: This ENDFOR corresponds to the FOR that began on line 6, Number is incremented by 1, and the test of remainder is repeated with this new number.

When I run the program the output on my screen looks like:

DSPLY  2 is prime
DSPLY  3 is prime
DSPLY  4 not prime
DSPLY  5 is prime
DSPLY  6 not prime
DSPLY  7 is prime 
DSPLY  8 not prime
DSPLY  9 not prime
DSPLY  10 not prime
DSPLY  11 is prime

Perfect results from a program simple enough for any interviewer.

Now if I was doing this for my own use in a business environment I would place the logic into an external procedure. I am going to give two example procedures. The first is the equivalent of the above program, and the second was another way I came up with reduce the number of checks of remainders I will need to do.

I placed both of the procedures into the same source member. The "global" area, common to all the procedures, in this member looks like:

01  **free
02  ctl-opt nomain ;

03  /define IsItPrime1
04  /define IsItPrime2
05  /include devsrc,copybook
06  /undefine IsItPrime1
07  /undefine IsItPrime2

Line 2: I need to use the NOMAIN control option so that the compiler knows that this procedure does not have a main procedure. Which it will not as the procedures in this source members will be called from other programs and procedures.

Lines 3, 4, 6, and 7: These are the compiler directives I must have to include only those procedure prototypes relevant to procedures in this source member. If I /DEFINE I always /UNDEFINE, it is not required just one of those things I feel I must do.

Line 5: /INCLUDE includes the relevant sections of code from the source member COPYBOOK when this member is compiled.

The first procedure that is similar to my previous program looks like:

08  dcl-proc IsItPrime1 export ;
09    dcl-pi *n char(1) ;
10      inNumber packed(3) const ;
11    end-pi ;

12    dcl-s Divisor uns(5) ;

13    if (inNumber < 2) ;
14      return 'E' ;
15    endif ;

16    for Divisor = 2 to (inNumber - 1) ;
17      if (%rem(inNumber:Divisor) = 0) ;
18        return 'N' ;
19      endif ;
20    endfor ;

21    return 'Y' ;
22  end-proc ;

Line 8: Start of the procedure. As this procedure will be exporting it results to other programs, modules, etc I need the EXPORT keyword after the procedure name.

Lines 9 - 11: I never bother to name my procedure interfaces, *N will do. A 3,0 packed parameter is passed to this procedure, line 10, and I use the CONST keyword to make this variable "read only", in other words I cannot change the value that is passed back to the calling program. The procedure returns a 1 character value, which is what the CHAR(1) on line 9 stands for.

Lines 13 – 15: As 1, zero, and negative numbers cannot be primes if the passed number is less than 2 then it is an "Error".

Lines 16 – 20: This is the same logic I used in the interview program to determine if the number is prime.

Line 21: If I have reached this point then I know that the number is a prime.

Then I started thinking about the numbers I was using as the divisor. I only need to check the remainder with prime numbers in the divisor, because if the number was not divisible by 2 it was not going to be divisible by 4, 6, 8, etc. So I created a second procedure using this method.

23  dcl-proc IsItPrime2 export ;
24    dcl-pi *n char(1) ;
25      inNumber packed(3) const ;
26    end-pi ;

27    dcl-ds *n ;
28      *n packed(3) inz(2) ;
29      *n packed(3) inz(3) ;
30      *n packed(3) inz(5) ;
31      *n packed(3) inz(7) ;
32      *n packed(3) inz(11) ;
33      *n packed(3) inz(13) ;
34      *n packed(3) inz(17) ;
35      *n packed(3) inz(19) ;
36      *n packed(3) inz(23) ;
37      *n packed(3) inz(29) ;
38      *n packed(3) inz(31) ;
39      *n packed(3) inz(37) ;
40      *n packed(3) inz(41) ;
41      *n packed(3) inz(43) ;
42      *n packed(3) inz(47) ;
43      *n packed(3) inz(53) ;
44      *n packed(3) inz(59) ;
45      *n packed(3) inz(61) ;
46      *n packed(3) inz(67) ;
47      *n packed(3) inz(71) ;
48      *n packed(3) inz(73) ;
49      *n packed(3) inz(79) ;
50      *n packed(3) inz(79) ;
51      *n packed(3) inz(83) ;
52      *n packed(3) inz(89) ;
53      *n packed(3) inz(97) ;
54      Primes packed(3) dim(26) pos(1) ascend ;
55    end-ds ;

56    dcl-s i packed(3) ;

57    if (inNumber < 2) ;
58      return 'E' ;
59    elseif (inNumber <= 100) ;
60      i = %lookup(inNumber:Primes) ;
61      if (i > 0) ;
62        return 'Y' ;
63      else ;
64        return 'N' ;
65      endif ;
66    else ;
67      for i = 1 to %elem(Primes) ;
68        if (%rem(inNumber:Primes(i)) = 0) ;
69          return 'N' ;
70        endif ;
71      endfor ;
72    endif ;

73    return 'Y' ;
74  end-proc ;

This is almost the same as my previous procedure, except...

Lines 27 – 55: I need an array of prime numbers, in this case from 2 – 100. The quickest way I could think to load an array with these values was to use a data structure, and then define an array to overlay the data structure's subfields, line 54. Notice that I did not give the data structure a name, I just gave it *N instead, which means it is nameless. The data structure subfields are also unnamed.

Lines 57 and 58: If the passed number is less than 2 it is an error.

Lines 59 - 65: If the passed number is less or equal to 100, then it is looked up in the array. If it is found return 'Y' as it is a prime, if it is not found return 'N'.

Lines 67 – 72: If the passed number is greater than 100 I do the same as I did in the interview program and the previous procedure, but using the prime numbers from the array only. If I find that remainder is 0 then it is not a prime, and return 'N'.

Line 73: I only reach here if the number is not, not a prime. By returning 'Y' it says that the number is a prime.

Now I have to define the procedure prototypes in the copybook member, COPYBOOK.

01  **free

02  /if defined(IsItPrime1)
03  //Values returned E = Error, number less than 2
04  //                N = Not a prime number
05  //                Y = Is a prime number
06  dcl-pr IsItPrime1 char(1) ;
07    *n packed(3) const ;
08  end-pr ;
09  /endif

10  /if defined(IsItPrime2)
11  //Values returned E = Error, number less than 2
12  //                N = Not a prime number
13  //                Y = Is a prime number
14  dcl-pr IsItPrime2 char(1) ;
15    *n packed(3) const ;
16  end-pr ;
17  /endif

Lines 2 and 10: If the program or procedure has a /DEFINE that matches the tag in the /IF then the code between the /IF and its matching /ENDIF will be included into what is being compiled. In this code each snippet contains the procedure interface information for the procedures I have just created.

I compile the source member containing the procedures into a module.

CRTRPGMOD MODULE(MYLIB/PRIMESMOD)
            SRCFILE(MYLIB/DEVSRC)
            OPTION(*SRCSTMT) 
            DBGVIEW(*ALL)
            ALWNULL(*YES)

And add the module to my binding directory.

ADDBNDDIRE BNDDIR(MYLIB/BNDDIR)
             OBJ((PRIMESMOD *MODULE))

Last piece is a program to call these two procedures.

01  **free
02  ctl-opt option(*srcstmt) bnddir('BNDDIR') ;

03  /define IsItPrime1
04  /define IsItPrime2
05  /include devsrc,copybook
06  /undefine IsItPrime1
07  /undefine IsItPrime2

08  dcl-s Count packed(3) ;
09  dcl-s RtnChar char(1) ;

10  for Count = 1 to 11 ;
11    RtnChar = IsItPrime1(Count) ;

12    if (RtnChar = 'N') ;
13      dsply ('1: ' + %char(Count) + ' not prime') ;
14    elseif (RtnChar = 'Y') ;
15      dsply ('1: ' + %char(Count) + ' prime') ;
16    elseif (RtnChar = 'E') ;
17      dsply ('1: ' + %char(Count) + ' cannot be prime') ;
18    endif ;
19  endfor ;

20  for Count = 93 to 110 ;
21    RtnChar = IsItPrime2(Count) ;

22    if (RtnChar = 'N') ;
23      dsply ('2: ' + %char(Count) + ' not prime') ;
24    elseif (RtnChar = 'Y') ;
25      dsply ('2: ' + %char(Count) + ' prime') ;
26    elseif (RtnChar = 'E') ;
27      dsply ('2: ' + %char(Count) + ' cannot be prime') ;
28    endif ;
29  endfor ;

30  *inlr = *on ;

Line 2: These are two of my favorite control options. I always like to use the source statement number as the program sequence number. And I am giving the binding directory that my module is in.

Lines 3 – 7: Including the procedure prototypes into this program.

Lines 10 – 15: Call the first procedure to check numbers 1 – 11 for which of these numbers are primes.

Lines 20 – 22: Call the second procedure to check which numbers between 93 and 110 are primes.

Lines 11 and 21: The procedure is called passing it the number used in the FOR group. The value returned is placed in the variable RtnChar.

Lines 12 – 18 and 22 – 28: Display a message depending upon the value returned from the procedure.

When this program is compiled and run I see:

DSPLY  1: 1 cannot be prime
DSPLY  1: 2 prime
DSPLY  1: 3 prime
DSPLY  1: 4 not prime
DSPLY  1: 5 prime
DSPLY  1: 6 not prime
DSPLY  1: 7 prime
DSPLY  1: 8 not prime
DSPLY  1: 9 not prime
DSPLY  1: 10 not prime
DSPLY  1: 11 prime
    
DSPLY  2: 93 not prime
DSPLY  2: 94 not prime
DSPLY  2: 95 not prime
DSPLY  2: 96 not prime
DSPLY  2: 97 prime
DSPLY  2: 98 not prime
DSPLY  2: 99 not prime
DSPLY  2: 100 not prime
DSPLY  2: 101 prime
DSPLY  2: 102 not prime
DSPLY  2: 103 prime
DSPLY  2: 104 not prime
DSPLY  2: 105 not prime
DSPLY  2: 106 not prime
DSPLY  2: 107 prime
DSPLY  2: 108 not prime
DSPLY  2: 109 prime
DSPLY  2: 110 not prime

 

This article was written for IBM i 7.4, and should work for some earlier releases too.

4 comments:

  1. Perhaps they were looking for a simple recursive procedure as prime numbers are one of the first recursive procedures learned. Recursion is a tool that is not typically in an RPGer's toolbox, and might give the interviewer insight into the interviewee.
    This works for me:
    dcl-proc isPrime;
    dcl-pi *n ind;
    n int(10) const; // returns if n is prime
    d int(10) const; // current divisor to check
    end-pi;

    // base cases
    if n <= 2;
    return (n = 2);
    endif;

    if %rem(n: d) = 0;
    return *off;
    endif;

    if d * d > n;
    return *on;
    endif;

    return isPrime(n: d + 1);
    end-proc isPrime;

    // hat tip to geeksforgeeks.org/recursive-program-prime-number/

    ReplyDelete
  2. A little mistake in the program : line 50, You have the same value twice, this means that the table should only be 25 elements, which match my count of primes below 100.

    I did the count using recursive sql just for the fun of it :

    This sql stamtent lists alle primes from 1 to 100


    WITH NUMBERS (LEVEL, PRIME) AS
    ( SELECT * FROM (values(1,1))
    UNION ALL
    SELECT LEVEL + 1, LEVEL + 1 FROM NUMBERS WHERE LEVEL < 100
    )
    SELECT X.PRIME FROM (SELECT NUMBERS.LEVEL, NUMBERS.PRIME FROM NUMBERS ) AS X
    WHERE NOT EXISTS
    (SELECT 1 FROM NUMBERS Y WHERE Y.PRIME BETWEEN 2 AND SQRT(X.PRIME) AND MOD(X.PRIME, Y.PRIME) = 0)
    and X.PRIME > 1
    ORDER BY X.PRIME

    Best regard Jan

    ReplyDelete
    Replies
    1. Thank you for reporting that mistake. I have struck it out to show that it is there in error.

      Delete
  3. You only have to test divisors up to the square root of the number you're testing for primality, so you can bail out of the loop early if the element is > %SQRT(InNumber).

    ReplyDelete

To prevent "comment spam" all comments are moderated.
Learn about this website's comments policy here.

Some people have reported that they cannot post a comment using certain computers and browsers. If this is you feel free to use the Contact Form to send me the comment and I will post it for you, please include the title of the post so I know which one to post the comment to.