The Museum of HP Calculators

HP Forum Archive 20

[ Return to Index | Top of Index ]

The Prime Factors Kata
Message #1 Posted by Thomas Klemm on 23 June 2011, 3:52 a.m.

Quote:
The model of computation of Java bytecode is that of a stack-oriented programming language.

Let's see how we can use that with the following Java program for the Prime Factors problem:

package primeFactors;

import java.util.*;

public class PrimeFactors {
  public static List<Integer> generate(int n) {
    List<Integer> primes = new ArrayList<Integer>();

    for (int candidate = 2; n > 1; candidate++)
      for (; n%candidate == 0; n/=candidate)
        primes.add(candidate);

    return primes;
  }
}

I used the Java compiler to create a class file and javap to disassemble the code:

javac PrimeFactors.java 
javap -c PrimeFactors

That's the result:

Compiled from "PrimeFactors.java"
public class primeFactors.PrimeFactors extends java.lang.Object{
public primeFactors.PrimeFactors();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

public static java.util.List generate(int);
  Code:
   0:   new #2; //class java/util/ArrayList
   3:   dup
   4:   invokespecial   #3; //Method java/util/ArrayList."<init>":()V
   7:   astore_1
   8:   iconst_2
   9:   istore_2
   10:  iload_0
   11:  iconst_1
   12:  if_icmple   45
   15:  iload_0
   16:  iload_2
   17:  irem
   18:  ifne    39
   21:  aload_1
   22:  iload_2
   23:  invokestatic    #4; //Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
   26:  invokeinterface #5,  2; //InterfaceMethod java/util/List.add:(Ljava/lang/Object;)Z
   31:  pop
   32:  iload_0
   33:  iload_2
   34:  idiv
   35:  istore_0
   36:  goto    15
   39:  iinc    2, 1
   42:  goto    10
   45:  aload_1
   46:  areturn

}

Now it's straightforward to translate that to RPN:

STO 00              ; int n
2                   ; 8:   iconst_2
STO 02              ; 9:   istore_2
LBL 10              
RCL 00              ; 10:  iload_0
1                   ; 11:  iconst_1
X>=Y?               ; 12:  if_icmple   45
GTO 45              
LBL 15              
RCL 00              ; 15:  iload_0
RCL 02              ; 16:  iload_2
MOD                 ; 17:  irem
X#0?                ; 18:  ifne    39
GTO 39              
VIEW 02             ; 22:  iload_2
RCL 00              ; 32:  iload_0
RCL 02              ; 33:  iload_2
/                   ; 34:  idiv
STO 00              ; 35:  istore_0
GTO 15              ; 36:  goto    15
LBL 39              
1                   
STO+ 02             ; 39:  iinc    2, 1
GTO 10              ; 42:  goto    10
LBL 45              
RTN                 ; 46:  areturn

We can't return a list and so I decided to just view the factors.

Cheers
Thomas

      
Re: The Prime Factors Kata
Message #2 Posted by Eddie W. Shore on 26 June 2011, 11:30 a.m.,
in response to message #1 by Thomas Klemm

Really cool. When I was checking out the link I thought you managed to work a prime factors program in PowerPoint. LOL

            
Re: The Prime Factors Kata
Message #3 Posted by Thomas Klemm on 27 June 2011, 3:32 p.m.,
in response to message #2 by Eddie W. Shore

When you run the disassembly through this script a lot of the translation is done:

#!/usr/bin/perl -w

while (<>) {

    printf "%-22s; $_%s",

    /[adfil]?return/        ? 'RTN' :
    /dup/                   ? 'ENTER' :
    /swap/                  ? 'X<>Y' :
    /[dfil]const_(\d)/      ? $1 :
    /iconst_m1/             ? -1 :
    /[dfil]load_(\d)/       ? "RCL 0$1" :
    /[dfil]load\s+(\d+)/    ? sprintf("RCL %02d", $1) :
    /[dfil]store_(\d)/      ? "STO 0$1" :
    /[dfil]store\s+(\d+)/   ? sprintf("STO %02d", $1) :
    /goto\s+(\d+)/          ? sprintf("GTO %02d", $1) :
    /iinc\s+(\d+),\s+(\d+)/ ? ($2, sprintf "STO+ %02d\n", $1) :
    /[dfil]add/             ? '+' :
    /[dfil]sub/             ? '-' :
    /[dfil]mul/             ? '*' :
    /[dfil]div/             ? '/' :
    /[dfil]rem/             ? 'MOD' :
    /ifeq\s+(\d+)/          ? ('X=0?',  sprintf "GTO %02d\n", $1) :
    /ifne\s+(\d+)/          ? ('X#0?',  sprintf "GTO %02d\n", $1) :
    /iflt\s+(\d+)/          ? ('X<0?',  sprintf "GTO %02d\n", $1) :
    /ifge\s+(\d+)/          ? ('X>=0?', sprintf "GTO %02d\n", $1) :
    /ifgt\s+(\d+)/          ? ('X>0?',  sprintf "GTO %02d\n", $1) :
    /ifle\s+(\d+)/          ? ('X<=0?', sprintf "GTO %02d\n", $1) :
    /if_icmpeq\s+(\d+)/     ? ('X=Y?',  sprintf "GTO %02d\n", $1) :
    /if_icmpne\s+(\d+)/     ? ('X#Y?',  sprintf "GTO %02d\n", $1) :
    /if_icmplt\s+(\d+)/     ? ('X>Y?',  sprintf "GTO %02d\n", $1) :
    /if_icmpge\s+(\d+)/     ? ('X<=Y?', sprintf "GTO %02d\n", $1) :
    /if_icmpgt\s+(\d+)/     ? ('X<Y?',  sprintf "GTO %02d\n", $1) :
    /if_icmple\s+(\d+)/     ? ('X>=Y?', sprintf "GTO %02d\n", $1) :
    '', ''

}

Labels are missing though. That's the output of the previous example:

                      ; Compiled from "PrimeFactors.java"
                      ; public class primeFactors.PrimeFactors extends java.lang.Object{
                      ; public primeFactors.PrimeFactors();
                      ;   Code:
                      ;    0:   aload_0
                      ;    1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
RTN                   ;    4:   return
                      ; 
                      ; public static java.util.List generate(int);
                      ;   Code:
                      ;    0:   new     #2; //class java/util/ArrayList
ENTER                 ;    3:   dup
                      ;    4:   invokespecial   #3; //Method java/util/ArrayList."<init>":()V
                      ;    7:   astore_1
2                     ;    8:   iconst_2
STO 02                ;    9:   istore_2
RCL 00                ;    10:  iload_0
1                     ;    11:  iconst_1
X>=Y?                 ;    12:  if_icmple       45
GTO 45
RCL 00                ;    15:  iload_0
RCL 02                ;    16:  iload_2
MOD                   ;    17:  irem
X#0?                  ;    18:  ifne    39
GTO 39
                      ;    21:  aload_1
RCL 02                ;    22:  iload_2
                      ;    23:  invokestatic    #4; //Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
                      ;    26:  invokeinterface #5,  2; //InterfaceMethod java/util/List.add:(Ljava/lang/Object;)Z
                      ;    31:  pop
RCL 00                ;    32:  iload_0
RCL 02                ;    33:  iload_2
/                     ;    34:  idiv
STO 00                ;    35:  istore_0
GTO 15                ;    36:  goto    15
1                     ;    39:  iinc    2, 1
STO+ 02
GTO 10                ;    42:  goto    10
                      ;    45:  aload_1
RTN                   ;    46:  areturn
                      ; 
                      ; }
                      ;

Far from perfect but maybe a good starting point.

Kind regards
Thomas

[ Return to Index | Top of Index ]

Go back to the main exhibit hall