The Prime Factors Kata



#4

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


#5

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


#6

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


Possibly Related Threads...
Thread Author Replies Views Last Post
  [WP 34s] Pressure Conversion Factors Timothy Roche 8 1,300 11-04-2013, 07:17 PM
Last Post: Dave Shaffer (Arizona)
  HP Prime: Conversion factors Paul Townsend (UK) 19 1,962 08-27-2013, 09:19 AM
Last Post: Nigel J Dowrick
  Finding prime factors on a "non-programmable" calculator Don Shepherd 6 868 09-05-2011, 10:11 AM
Last Post: Allen
  Is there an easy way to determine how many factors a number has? Don Shepherd 7 932 07-04-2011, 09:17 AM
Last Post: Gilles Carpentier
  factors and primes for 29c hal 2 412 02-01-2006, 05:38 PM
Last Post: Hal
  49G+ -- FACTORS Has Bug? Paul Brogger 8 892 10-27-2003, 04:56 PM
Last Post: Paul Fox

Forum Jump: