Java Forum / General / December 2006
Please help!
emilie - 22 Dec 2006 12:41 GMT I'm a beginner in java..this is actually my second program in java..can you help me with my code?? pleeaaassee??
/*Return the greatest common divisor */
class GCDSolver{ int n1, n2; int gcd=1;
public void GCDsolver(int a, int b){ n1=a; n2=b; }
public void solve(int a, int b){ gcd=getGCD(a, b); }
public int getGCD(int a, int b) { if (b==0) return a; else return getGCD(b, a % b); } }
class GCDMainProgram{ public static void main(String[] args){ //input two numbers int x = Console.readInt(); int y = Console.readInt(); //initialize object GCDSolver solver = new GCDSolver(x, y); solver.solve(x, y); System.out.println("Answer is" + solver.getGCD(x, y)); } }
Alex Hunsley - 22 Dec 2006 13:22 GMT > I'm a beginner in java..this is actually my second program in java..can > you help me with my code?? pleeaaassee?? For starter, put something actually descriptive in the subject line. "Please help" doesn't tell us anything about the subject of your email.
Seconds, "help me with my program" is a bit of a vague question, try being more specific.
emilie - 24 Dec 2006 05:44 GMT > > I'm a beginner in java..this is actually my second program in java..can > > you help me with my code?? pleeaaassee?? [quoted text clipped - 4 lines] > Seconds, "help me with my program" is a bit of a vague question, try > being more specific. actually, my assignment is just to fill up some missing informations. the only problem with my code is the console.readInt. Everytime i compile it, an error appears regarding it..thanks!
ck - 22 Dec 2006 14:00 GMT I don't know what algorithm you were trying to use So I wrote a program on Euclid's Algorithm ==== Code Start ==== /** * @date Dec 22, 2006 * @author CK * @copyright (c) http://www.gfour.net */ public class GCD {
public int getGcdByEuclidAlgo(int a, int b) { //boolean flag = false; int remainder=2; int number=0; int divisor=0; int previousDivisor =0 ; //just swapping the numbers if (a<b){ a=a+b; b=a-b; a=a-b; }
if (a > b) {
number=a; divisor=b; while (remainder >1) { previousDivisor = divisor; remainder = number % divisor; System.out.println(remainder); System.out.println(divisor); if (remainder > b) { a = a % b; remainder = a;
}else { number = b; divisor = remainder; }
} } if (remainder==1) return 1; return previousDivisor; }
/** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int num1 = 1002; int num2 = 24; System.out.println("GCD= " + (new GCD()).getGcdByEuclidAlgo(num1, num2)); }
}
==== Code End ==== Hope this helps.
Cheers, Ck http://www.gfour.net
> I'm a beginner in java..this is actually my second program in java..can > you help me with my code?? pleeaaassee?? [quoted text clipped - 32 lines] > } > } ck - 22 Dec 2006 14:04 GMT You can remove System.out.println lines from the method getGcdByEuclidAlgo. I have used them to test the program at the time of coding. The implementation of the algorithm is not very good. I hope someone can improve it.
Cheers, Ck http://www.gfour.net
Oliver Wong - 22 Dec 2006 15:19 GMT > You can remove System.out.println lines from the method > getGcdByEuclidAlgo. I have used them to test the program at the time of > coding. > The implementation of the algorithm is not very good. I hope someone > can improve it. There's a recursive algorithm for calculating GCD which is about 4 statements long. I hesitate to post it, in case it's a homework assignment. If you, ck, want to see it, e-mail me.
- Oliver
Luc The Perverse - 22 Dec 2006 17:04 GMT >> You can remove System.out.println lines from the method >> getGcdByEuclidAlgo. I have used them to test the program at the time of [quoted text clipped - 5 lines] > statements long. I hesitate to post it, in case it's a homework > assignment. If you, ck, want to see it, e-mail me. "In case"? I think "since" and "obviously" are better words to describe the homework - like nature of what's going on here.
-- LTP
:) Oliver Wong - 22 Dec 2006 17:58 GMT >>> You can remove System.out.println lines from the method >>> getGcdByEuclidAlgo. I have used them to test the program at the time of [quoted text clipped - 8 lines] > "In case"? I think "since" and "obviously" are better words to describe > the homework - like nature of what's going on here. The OP, who presumably was assigned the homework, is emilie. CK is an "innocent bystander", and I'm willing to send the solution to the latter, but not the former.
- Oliver
Oliver Wong - 22 Dec 2006 18:02 GMT >> "Oliver Wong" <owong@castortech.com> wrote in message >>> There's a recursive algorithm for calculating GCD which is about 4 [quoted text clipped - 7 lines] > "innocent bystander", and I'm willing to send the solution to the latter, > but not the former. Actually, after re-looking at the OP, it contains the algorithm I was thinking of anyway, so there's no harm in posting it, I guess.
public int getGCD(int a, int b) { if (b==0) return a; else return getGCD(b, a % b); }
- Oliver
John Ersatznom - 23 Dec 2006 12:53 GMT > public int getGCD(int a, int b) { > if (b==0) > return a; > else > return getGCD(b, a % b); > } Cute, considering I took only ten minutes the other day to implement a bignum binary gcd for some project where there was no decently-performing gcd implementation in the bignum library used. (Now I wonder if Java's BigInteger's is any better...system libraries have a tendency towards having at least one shoddy algo. Actually, two, since the RNG invariably blows. I don't know of a single exception to that rule -- most system library RNGs don't even seem to be uniform. Java's is, but independence? Forgeddaboudit. Pairs or trios of successive values tend to clump on lines and planes, which tells me that someone at Sun thought using a linear congruential RNG was clever. (And they use it for cryptography! One random number leaking clues about the next one can open up all kinds of attack opportunities for session-ID spoofing and things like that.) I ended up implementing the MT in Java just to get decent random numbers.)
Mark Thornton - 23 Dec 2006 13:09 GMT > Sun thought using a linear congruential RNG was clever. (And they use it > for cryptography! One random number leaking clues about the next one can I believe the crypto routines use a different "secure" random number generator. The regular use, random number generators are always a compromise between quality and performance. I think the java.util.Random implementation is a reasonable one in this context.
Mark Thornton
John Ersatznom - 24 Dec 2006 13:59 GMT >> Sun thought using a linear congruential RNG was clever. (And they use >> it for cryptography! One random number leaking clues about the next [quoted text clipped - 4 lines] > compromise between quality and performance. I think the java.util.Random > implementation is a reasonable one in this context. MT isn't exactly slow, you know.
Arne Vajhøj - 24 Dec 2006 14:08 GMT >>> Sun thought using a linear congruential RNG was clever. (And they use >>> it for cryptography! One random number leaking clues about the next [quoted text clipped - 6 lines] > > MT isn't exactly slow, you know. True.
But it was invented 2 years after Java 1.0 was released.
And since the java docs explicit specifies the algorithm, then it would have been a problem to change it.
They could have added a new one later, but it has apparently not been prioritized.
Arne
Daniel Dyer - 24 Dec 2006 14:26 GMT > But it was invented 2 years after Java 1.0 was released. > [quoted text clipped - 5 lines] > > Arne Unfortunately, the initial implementation was flawed and, for the reasons you highlight, we are stuck with it.
From Roedy Green's page on pseudorandom numbers (http://mindprod.com/jgloss/pseudorandom.html):
"Unfortunately, even if you do everything perfectly to use java.util.Random, the generator itself is flawed. It falls into the trap Knuth says to avoid — using a power of two for the modulus. The random numbers it generates are not all that random. It is blindingly obvious when you plot the low order bits of the random numbers visually."
Dan.
 Signature Daniel Dyer https://watchmaker.dev.java.net - Evolutionary Algorithm Framework for Java
Daniel Dyer - 24 Dec 2006 14:24 GMT >>> Sun thought using a linear congruential RNG was clever. (And they use >>> it for cryptography! One random number leaking clues about the next [quoted text clipped - 5 lines] > > MT isn't exactly slow, you know. To put some figures on this, the Java port of the Mersenne Twister that I use for my Watchmaker project is about 20% quicker than java.util.Random and, unlike java.util.Random, the Diehard tests do not flag any issues with the output.
Dan.
 Signature Daniel Dyer https://watchmaker.dev.java.net - Evolutionary Algorithm Framework for Java
Mark Thornton - 24 Dec 2006 15:16 GMT >>> Sun thought using a linear congruential RNG was clever. (And they use >>> it for cryptography! One random number leaking clues about the next [quoted text clipped - 6 lines] > > MT isn't exactly slow, you know. Isn't a little slow to initialise or am I thinking of something else?
John Ersatznom - 24 Dec 2006 16:39 GMT >>>> Sun thought using a linear congruential RNG was clever. (And they >>>> use it for cryptography! One random number leaking clues about the [quoted text clipped - 8 lines] > > Isn't a little slow to initialise or am I thinking of something else? Fortunately, initialization isn't usually the first place you go looking for a performance hotspot. In fact, there's three major areas were random numbers are used extensively: 1. Security/crypto apps and 2. games -- I/O wait times dominate both fields 3. Mathematics (simulations, monte carlo integration...) -- crunching speed becomes important, but it's calls to the next() method in innermost loops that will predominate over constructing new instances on far rarer occasions, or possibly even only once.
Thomas Hawtin - 23 Dec 2006 14:28 GMT > Cute, considering I took only ten minutes the other day to implement a > bignum binary gcd for some project where there was no > decently-performing gcd implementation in the bignum library used. (Now > I wonder if Java's BigInteger's is any better...system libraries have a I believe it has improved since the original version.
> tendency towards having at least one shoddy algo. Actually, two, since > the RNG invariably blows. I don't know of a single exception to that [quoted text clipped - 6 lines] > things like that.) I ended up implementing the MT in Java just to get > decent random numbers.) java.util.Random may not be the best designed class, but it is not used for crypto (not by anyone with half a brain, anyway). Perhaps you were looking for this:
http://java.sun.com/javase/6/docs/api/java/security/SecureRandom.html
"A cryptographically strong random number minimally complies with the statistical random number generator tests specified in FIPS 140-2, Security Requirements for Cryptographic Modules, section 4.9.1. Additionally, SecureRandom must produce non-deterministic output. Therefore any seed material passed to a SecureRandom object must be unpredictable, and all SecureRandom output sequences must be cryptographically strong, as described in RFC 1750: Randomness Recommendations for Security."
Tom Hawtin
emilie - 24 Dec 2006 05:41 GMT > >> "Oliver Wong" <owong@castortech.com> wrote in message > >>> There's a recursive algorithm for calculating GCD which is about 4 [quoted text clipped - 19 lines] > > - Oliver actually, my assignment is just to fill up some missing informations. the only problem with my code is the console.readInt. Everytime i compile it, an error appears regarding it..thanks!
emilie - 24 Dec 2006 05:41 GMT > >> "Oliver Wong" <owong@castortech.com> wrote in message > >>> There's a recursive algorithm for calculating GCD which is about 4 [quoted text clipped - 19 lines] > > - Oliver actually, my assignment is just to fill up some missing informations. the only problem with my code is the console.readInt. Everytime i compile it, an error appears regarding it..thanks!
ck - 22 Dec 2006 17:10 GMT Ya I thought so. I am sorry but I am too drunk to use my head right now. But for sure I would be interested to try that out. let me try it for myself. You can mail me at ck-at-gfour.net
cheers, Ck http://www.gfour.net
> > You can remove System.out.println lines from the method > > getGcdByEuclidAlgo. I have used them to test the program at the time of [quoted text clipped - 7 lines] > > - Oliver Oliver Wong - 22 Dec 2006 15:15 GMT > I'm a beginner in java..this is actually my second program in java..can > you help me with my code?? pleeaaassee?? [code snipped]
Yes, we can probably help you. What are you having difficulty with?
- Oliver
jupiter - 24 Dec 2006 15:57 GMT >> I'm a beginner in java..this is actually my second program in >> java..can [quoted text clipped - 5 lines] > > - Oliver actually, my assignment is just to fill up some missing informations. the only problem with my code is the console.readInt. Everytime i compile it, an error appears regarding it..thanks!
Oliver Wong - 27 Dec 2006 17:24 GMT >>> I'm a beginner in java..this is actually my second program in java..can >>> you help me with my code?? pleeaaassee?? [quoted text clipped - 5 lines] > the only problem with my code is the console.readInt. Everytime i > compile it, an error appears regarding it..thanks! It might be easier to help you if you stated the error message.
- Oliver
RedGrittyBrick - 22 Dec 2006 18:46 GMT "Please help!" is an awful subject line. Can I suggest that next time you try to put a brief description of the problem in the subject. For example "simple recursive method for greatest common divisor"
> I'm a beginner in java..this is actually my second program in java..can > you help me with my code?? pleeaaassee?? To get the best out of newsgroups I find it is a good idea to clearly state what your program did and what you actually expected it to do.
> /*Return the greatest common divisor */ I'd include some comments explaining how the class should be used.
> class GCDSolver{ I'd put a comment here explaining the algorithm to be used. If it is a classic maths algorithm you could give it's name or the person who invented it.
> int n1, n2; You assign to n1 and n2 in your constructor but never use them. These declarations could be removed without affecting your program's output.
If you are planning to use n1 and n2 in your methods, it is good object-oriented practice to declare them as private.
> int gcd=1; I'm not convinced that 1 is a better default value than 0 or null.
> public void GCDsolver(int a, int b){ > n1=a; n2=b; [quoted text clipped - 3 lines] > gcd=getGCD(a, b); > } You don't need to pass a and b to solve() since you already have n1 and n2. You could write this as public void solve() { gcd = getGCD(n1, n2); }
> public int getGCD(int a, int b) { Again, you don't need to pass a and b. public int getGCD() { if (n2 == 0) // etc
> if (b==0) > return a; > else > return getGCD(b, a % b); > } > }
> class GCDMainProgram{ > public static void main(String[] args){ > //input two numbers > int x = Console.readInt(); > int y = Console.readInt(); > //initialize object You don't need a comment like that. Comments like the following are completely useless for me // assign 1 to a a = 1; I find it useful for comments to explain WHY you are doing something. Too many comments impede readability.
> GCDSolver solver = new GCDSolver(x, y); > solver.solve(x, y); I imagine that if you made getGCD static, you could delete the above two lines and replace the line below with System.out.println("Answer is " + GCDSolver.getGCD(x, y));
> System.out.println("Answer is" + solver.getGCD(x, y)); > } > } Your algorithm looks fishy, I'd try the following version of your code, stare at the DEBUG output and try to think why.
/* * A library of many useful maths routines. Currently only GCD. */ public class MathRoutines { /* * Return the greatest common divisor of two integers. * 'int a = GCD(8, 12);' should assign 4 to a. * However, GCD has a bug! */ static int GCD(int a, int b) { System.out.println("a=" + a + ", b=" + b); // DEBUG if (b == 0) return a; else return GCD(a, a % b); }
/* * This main() is included for test purposes. It can be left * in place even if this class is used by another class * which has it's own main() */ public static void main(String[] args) { // Test whether order of arguments matters, it shouldn't. System.out.println("The GCD of 8 and 12 is " + GCD(8, 12)); System.out.println("The GCD of 12 and 8 is " + GCD(12, 8)); } }
emilie - 24 Dec 2006 05:39 GMT > "Please help!" is an awful subject line. Can I suggest that next time > you try to put a brief description of the problem in the subject. For [quoted text clipped - 112 lines] > } > } actually, my assignment is just to fill up some missing informations. the only problem with my code is the console.readInt. Everytime i compile it, an error appears regarding it..thanks!
RedGrittyBrick - 24 Dec 2006 13:00 GMT <snip: source code for program to calculate Greatest Common Divisor of two integers using the Euclidian algorithm>
> actually, my assignment is just to fill up some missing informations. You posted this identical message to a half dozen reponses in this thread. That means I have read this exact same text many times over. Try to imagine the effect that has on how people feel about helping you.
> the only problem with my code is the console.readInt. Everytime i > compile it, an error appears regarding it..thanks! To get the best out of newsgroups I find I need to be specific. Exactly what error message did you get? Using cut & paste prevents typing errors and saves time.
You might like to read some guidelines on getting the best out of newsgroups ... http://www.catb.org/~esr/faqs/smart-questions.html
I loaded your original code into Eclipse and it said "Console cannot be resolved" at this line: int x = Console.readInt(); I looked up the Javadocs for Console at http://java.sun.com/javase/6/docs/api/java/io/Console.html and noted that it says "Since: 1.6".
I am using 1.5. That explains that error I guess.
I therefore changed the start of the program as follows public static void main(String[] args) throws IOException { InputStreamReader stdin = new InputStreamReader(System.in); BufferedReader console = new BufferedReader(stdin); String s = console.readLine(); int x = Integer.parseInt(s);
Ditto for y.
Eclipse said "The constructor GCDSolver(int, int) is undefined" at this line: GCDSolver solver = new GCDSolver(x, y); So I changed public void GCDsolver(int a, int b){ to GCDSolver(int a, int b){ (Note the capital S)
After that it worked.
Merry Xmas!
Hemal Pandya - 22 Dec 2006 18:52 GMT > I'm a beginner in java..this is actually my second program in java..can > you help me with my code?? pleeaaassee?? I don't want to solve your class assignment for you, it's almost solved any way. But I'll try to ask some question that might help you to the finishing line. I am curious if you wrote that getGCD method all by yourself, from an algorithm described in English, or you copied it from someone else's notebook. If latter, you might as well skip the rest of this post because you will not be able make sense of it.
> /*Return the greatest common divisor */ What returns the GCD? A class does not 'return' anything, it has methods that return something.
> class GCDSolver{ > int n1, n2; Do you intend to hold on to the integers of which you want to calculate GCD? That would be the reason to have them as members.
> int gcd=1; Likewise, you would have gcd as a member only if you want to hold on to the gcd and return it at some point after calculating the gcd. Is that what you are trying to do?
> public void GCDsolver(int a, int b){ > n1=a; n2=b; > } You assign the member variables in the constructor, almost. But these two variables, n1 and n2 are never used by any of the methods! Why do you need the member variables?
I say almost above because as written, this method is not a constructor. Constructors do not have return types. How would you change this so that it becomes constructor, if you decide that you do need such a ctor?
> public void solve(int a, int b){ > gcd=getGCD(a, b); > } The calculated gcd is not used by any other method. What is the purpose?
> public int getGCD(int a, int b) { > if (b==0) > return a; > else > return getGCD(b, a % b); > } This is method that works. It is called by the main method of GCDMainProgram and returns the correct gcd. But it does not use any member variables of the class! Such a method is typically declared 'static' (look up what it means).
> } > [quoted text clipped - 3 lines] > int x = Console.readInt(); > int y = Console.readInt(); I assume Console is some class that allows console io. But you will have to 'import' it. Look up what that means.
> //initialize object Do you need to?
> GCDSolver solver = new GCDSolver(x, y); > solver.solve(x, y); What does this method do for the rest of the code in this method?
> System.out.println("Answer is" + solver.getGCD(x, y)); > } > } You have two choices:
1. Accept the two integers of which you want to calculate the gcd in constructor and provide another method that returns previously calculated gcd. If you take this route, you have to ensure gcd has been calculated before client asks for it. One way to do this is to calculate it in the constructor itself, possibly by calling the solve method. If not, can you ensure that without using one more variable?
2. Get rid of the constructor and provide the functionality in a single method.
And here are two bonus questions:
1. Why is the first choice above more appropriate if you have need the gcd of the same pairs repeatedly?
2. How would you generalize the above for finding GCD of more then 2 numbers?
emilie - 24 Dec 2006 05:36 GMT > > I'm a beginner in java..this is actually my second program in java..can > > you help me with my code?? pleeaaassee?? [quoted text clipped - 97 lines] > 2. How would you generalize the above for finding GCD of more then 2 > numbers? actually, my assignment is just to fill up some missing informations. the only problem with my code is the console.readInt. Everytime i compile it, an error appears regarding it..thanks!
Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
|
|