Member Avatar for joankim

First I would like to state that I am almost positive that this is a bug in Java, not a coding mistake by me.

This program is designed to print the first n (inputted) square triangular numbers (STN's). A STN is a number that is both a perfect square and a triangular number. You find triangular numbers by going: 1+2+3+4 etc. The first trangular numbers are: 1,3,6,10 and the first STN are: 1,36,1225 etc. I noticed that my program does print all the STN's, but starts failing when the values get higher. The part that's failing is the part that checks if a perfect square is a STN. Consider the following code:

while(x > total){                     //Will run until total == x || total < x.
            incrementer++;          //Increments total with a higher number each time
            total += incrementer;   /* Total is always triangular numbers. x has to match total for it to be a square triangular number.*/
            //System.out.println(total) //For troubleshooting, disabled
            }

The first values of incrementer and total will be
incrementer: 1,2,3,4,5
total: 1,3,6,10

The whole program outputs the first STN's correctly, but starts failing when the numbers gets high. Here is the outputprinting 10 STN's:
Square triangular number # 1: 1
Square triangular number # 2: 36
Square triangular number # 3: 1225
Square triangular number # 4: 41616
Square triangular number # 5: 1413721
Square triangular number # 6: 18705624
Square triangular number # 7: 43099224

All the STN's from #6 and up is incorrect.

So, for the troubleshoot part. I have figured out that everything works as it should, except the while loop above, which starts failing after STN #5. So I made another program to check if and where this while loop is failing. Everything that is printed bySystem.out.println(total)
is read into this other program. In this program, each value is subtracted by the previous value. By doing this, we are finding out how much total in incremented by for each time it runs through the while loop. The result should be 1,2,3,4,5,6 and so on. It is correct for the first couple of thousand values, but it starts failing at 5792.0. Here is a copy from the output in the area where it starts failing:
5798.0
5796.0
5794.0
5796.0
5792.0
5792.0
5791.0
5790.0
5789.0
5788.0

As you can see, everything is going smoothly until it reaches 5792.0. Everything described so far is using floats. If I try with longs, it starts failing at STN #5, and turns negative at STN #9. For doubles and its, it works actually until #7, but then they reach their maximum value.

So my question to you guys is: Why is the compiler failing here? And can I code this in a different way to avoid the bug in the compiler?

In case you want to see my code, I will paste it here. Program number one is the one actually finding the STN's, while program number 2 is just for troubleshooting (finding out if/when/how the while loop is failing by printing how much total is incremented with for each time)

#1:

  import java.util.*;
import java.lang.*;
import java.math.*;

public class FunLoops {
    long x;
    int a = 0;
    long b = 1;
    float incrementer = 0;
    long total = 0;
    Scanner in;

    public FunLoops(){
        in = new Scanner(System.in);
        loops();
    //  lcm();
    }

public void loops(){
Scanner in = new Scanner(System.in);
System.out.println("How many square triangular numbers do you want?");
int input = in.nextInt();
System.out.println();

/*if(input > 8){                    //Limits square triangular numbers to 8, disabled.
    input = 8;
    System.out.println("Will print 8 of them");
    }*/

while(a < input){                    //Will run until desired number of square triangular numbers is found
//  System.out.println("Power of: " + b);   //For troubleshooting, disabled
x = b*b;                            //x will only be perfect squares of b.
b++;

        while(x > total){           //will run until total == x || total < x.
            incrementer++;          //Increments total with a high number each time
            total += incrementer;   // Total has to match x at one point for it to be a perfect square.
            //System.out.println(total) //For troubleshooting, disabled
            }

        if (total == x){            // Checks if perfect square IS a square triangular numbers.
            a++;                    // stops the first while loop when it has reached input.
            System.out.println(" Square triangular number # " + a + ": " + (int)x); // prints all square triangular numbers
            }
        } // End of first while loop

    System.out.println();
    } // end of loops()
2:
import java.io.*;
import java.util.*;

public class Store {
    private ArrayList <Item> myStore = new ArrayList <Item>();
    Scanner in;


    public Store(){
        readFile();

    }

    public void readFile(){

    try{
    float myNums;
    in = new Scanner(new File("abc.txt")); //abc contains all the printed values of total in program #1
    while(in.hasNextInt()){
        myNums = in.nextFloat();
        myStore.add(new Item(myNums));

    }}catch(Exception e){
        System.out.print(" Error: " + e.getMessage());
        }
        for(int i = 0; i < myStore.size()-1; i++){
            float check1 = myStore.get(i+1).getNums()-myStore.get(i).getNums() //Prints every value - the prev.
            System.out.println(check1);
        }
    }
}

______________________________________________________________________________________________

public class Item {
    public float myNums;

    public Item(float nums){
        myNums = nums;
    }

    public float getNums(){
    return myNums;
    }
}

PS: I almost finished writing this, and then google chrome CRASHED(!) and i had to start over. Not fun.

How many digits in the number that did not print? Are you using int or long variables? Do you know the largest number that an int will hold? 2147483647

Member Avatar for joankim

When floats are used, the first incorrect square triangular number is 18705624, while the first time the while loop i mentioned starts malfunctioning is when total has the value 16776528 (might be an off by one error here, in which case the correct value is either 16770736 or 16782321) and iterator has the value 5792. After the first incorrect STN is printed, it keeps on printing higher and higher values, all of them incorrect.

When ints are used, it starts malfunctioning on the same square triangular number as with floats.

When doubles are used, it works correctly until #8. On the eighth, it has reached the max value, and all the square triangular numbers printed after this is MAX_VALUE (which is not a STN)

For longs, it prints correctly until square #7 (1631432881). After that the next ones printed are -413881792, 1476455377, -926242940, 1391023033, 976385808

And to answer your first question, it has yet to happen that something does not print, even with doubles and ints.

EDIT: When using doubles, it keeps on printing the max value of doubles when the numbers eventually go that high.
With ints, I have yet to see what happen when it reaches the max value of ints, because the program keeps on running without printing any more than #7. I am not sure it it will ever print #8.

Have you tried using bigint?

Member Avatar for joankim

I have never used those before, but I gave it a try, and it works! Now, I still wonder why longs and floats screwed up... Any ideas? I think it's pretty clear right now that this was not a mistake on my part, as BigInts worked.

These are just guesses.
I've tried only two types for incrementer (float and long), and kept total as long. The thing is, when incrementer was float which is 4 bytes, it probably converts total from long (8 bytes) into float, add incrementer to it, then convert back to long. Maybe the conversion causes loss of the upper bits and therefore gives out an incorrect value. It probably goes the same with int, which is also 4 bytes. (I've never tried int in your program). That is probably why these two types give the wrong output despite total not reaching its max value. With incrementer as long or double, which is another type with 8 bytes, total will not be converted down, and thus, no loss of accuracy. However, they may reach maximum value and give out the wrong output. (For long, you and I both have experienced having negative output, which means that, being signed, it exceeded the max positive value) (For double, I have not tried it but you said it kept printing out the max value)

Member Avatar for joankim

Sounds very reasonable. However, I have always kept all my data types the same. If one of the variables is a long, all of them are longs, so that the program never needs to convert anything. If I want to try with a different data type, I change ALL the variables.

Also, when long turned negative, it was not even close to its max value. Max value for long is 9223372036854775807. Long turned negative already in the millions or billions.

Probably because at line 43, you used int(x) instead of just x? x at that point far exceeds the max value for an integer.
Also, at the example you posted above, total/x are long and incrementer is float.

while(x > total){ //Will run until total == x || total < x.

hmm i havent checked through all your code but i see this mistake is repeated:

` while(x > total){                     //Will run until total == x || total < x.`

can you see the mistake? you say it will run until x==total||x<total but you are using while(x>total) which will loop only while x is greater then the total??

Member Avatar for joankim

That (int)x is probably it. Can't beleive I didn't catch that. Oh well. And i guess that was a bad example, normally, I didnt do that.

By the way, this program was written by me quite a while ago, when I was new to Java. And the posted example is a revised version. But I decided to start from scratch and see how effifient I can make it. I am now using a recursive math formula. This program finds the first 30 square triangular numbers instantly, and seems to be working for infinitely high numbers. The highest number I have reached is: 21491557980090694297098458060768809299959232538764024564150512761 which equals 2*10^64.
Pretty high, considering that there are between 10^78 and 10^82 atoms in the universe :)

Here is the last and finished version of my program. Feel free to input on how I can make it even more efficient. Maybe move the if/if else/else statements around, or do something differently with the BigInts? (I'm still new to those date types)
Is it more efficient to use .valueOf(int) instead of creating the variables?

import java.util.*;
import java.lang.*;
import java.math.*;

public class FunLoops {
    Scanner in;
    BigInteger two = new BigInteger("2");
    BigInteger one = new BigInteger("1");
    BigInteger zero = new BigInteger("0");
    BigInteger received = new BigInteger("0");
    BigInteger total = new BigInteger("0");

    BigInteger thirtyfour = new BigInteger("34");
    int input;

    public FunLoops(){
        in = new Scanner(System.in);
        run();
    }
    public void run(){
        System.out.println("How many square triangular numbers do you want printed?");
        input = in.nextInt();
        for(int i=0; i < input; i++){
            System.out.println("Square Triangular Number #" + (i+1) + ": " + rec(BigInteger.valueOf((long)i)));
        }

    }

    public BigInteger rec(BigInteger received){
        if(received.equals(zero)){
            return zero;
        }else if(received.equals(one)){
            return one;
        }else{

            total = thirtyfour.multiply(rec(received.subtract(one))).subtract(rec(received.subtract(two))).add(two);
                //  34           *       rec(received-1)                -       rec(received-2)           +   2    ;
        }
    return total;
    }
}
Member Avatar for joankim

Sorry cOrRuPtG3n3t!x, I didnt see your post until now. Yes, I see the mistake, but the mistake is only in the notes, marked by //. I tend to be more sloppy with those :)

I would be very interested, however, in input about how to improve the efficiency of this last program.

It should already be very good, but one think I am thinking is that for each number outputted, it looks like it is going to start the recursion all over again. (is this correct?) If I somehow could make it "save" the previous two recursions, it would save the program from doing the vast majority of calculations.

What I'm thinking is:
When rec(3) is called, it is going to do the current calculation, and it is going to do rec(2) and then rec(1) and rec(0) and then rec(1) again.
Similarly, for rec(4), it will do: rec(3){ rec(2){ rec(1),rec(0) } rec(1)} rec(2){ rec(1),rec(0)}

Wouldn't it save A LOT of time if, when a recursion is called, the result is somehow stored? So that when rec(4) is called, and needs rec(3) and rec(2), those values are remembered?

Create a dynamic bigint array, initialize it with size input, and modify the rec function. I have actually created the code, just have to test it. I'll post it if it works. By the way, did you really get the first 30 stns instantly? I got the first 10 instantly, had to wait a couple of seconds for 11th, a little longer for 12th and I didn't have the patience to wait for 13th.

commented: thanks for doing this with me :) +1
Member Avatar for joankim

Haha, yeah. Processor power and memory usage matter a lot, tho. My laptop runs 2.27 GHz with 6GB memory. First 35 was instant when I wrote that, but now that I have a bunch of stuff running, it takes like a second. I did try to leave it on for a couple of hours, closing down everything else and setting priority to high. I got to 50.

Ok. I tried the code, typed in 50 as input and got the first 50 in an instant. Even with 100 as input, it gives out everything instantaneously.

Member Avatar for joankim

Can you post the code please? I made an attempt, and it also does 100 instantly.

import java.util.*;
import java.lang.*;
import java.math.*;
public class FunLoops {
    Scanner in;
    BigInteger two = new BigInteger("2");
    BigInteger one = new BigInteger("1");
    BigInteger zero = new BigInteger("0");
    BigInteger received = new BigInteger("0");
    BigInteger total = new BigInteger("0");
    BigInteger [] array;
    BigInteger thirtyfour = new BigInteger("34");
    int input;
    public FunLoops(){
        in = new Scanner(System.in);
        run();
    }
    public void run(){
        System.out.println("How many square triangular numbers do you want printed?");
        input = in.nextInt();
        array = new BigInteger[input];
        array[0] = zero;
        array[1] = one;
        for(int i=0; i < input; i++){
            BigInteger[] array2 = rec(i);
            System.out.println("Square Triangular Number #" + (i+1) + ": " + array[i]);
        }
    }
    public BigInteger[] rec(int received){
        if(received == 0){
            return array;
        }else if(received == 1){
            return array;
        }else{
            array[received] = thirtyfour.multiply(array[received - 1]).subtract(array[received - 2]).add(two);
                                //  34           *       rec(received-1)                -       rec(received-2)           +   2    ;
        }
    return array;
    }
}
Member Avatar for joankim

I decided to optimize this a little more. I would, however, really like to see your code, to compare our different approaches to the problem.

It now shortens the big numbers to.... kinda standard form.
An example output is STN #3255: 5048*10^4977

That's the highest I have made it go. It takes maybe 5 seconds for the first 1000, then maybe 10 for the next thousand. I'm posting the finished code. I'd say this is fully optimized to the best of my abilities, and it is not likely I will ever change it again. EDIT: Damn, I just cant help myself :P

 import java.util.*;
import java.lang.*;
import java.math.*;

public class FunLoops {
    Scanner in;
    BigInteger base = new BigInteger("0");
    BigInteger exponent = new BigInteger("0");
    BigInteger total = new BigInteger("0");
    BigInteger [] array;
    String [] array2;

    BigInteger thirtyfour = new BigInteger("34");
    int input;

    public FunLoops(){
        in = new Scanner(System.in);
        run();
    }
    public void run(){
        System.out.println("How many square triangular numbers do you want printed?");
        input = in.nextInt();
        array = new BigInteger[input];
        array2 = new String[input];
        array[0] = BigInteger.valueOf(0);
        array[1] = BigInteger.valueOf(1);
        for(int i=0; i < input; i++)
        {
            rec(i);

            if(array[i].compareTo(BigInteger.valueOf(10000)) == 1)
            {
                base = array[i];

                    while(base.compareTo(BigInteger.valueOf(10000)) == 1)
                    {
                        base = base.divide(BigInteger.valueOf(10));
                        exponent = exponent.add(BigInteger.valueOf(1));
                    }

                array2[i] = base.toString().concat("*10^" + exponent.toString());
                System.out.println("STN #" + (i+1) + ": " + array2[i]);
                exponent = BigInteger.valueOf(0);

            }else
            {
                System.out.println("STN #" + (i+1) + ": " + array[i]);
            }
        }

    }

    public void rec(int received)
    {
        if(received > 1)
        {
            array[received] = thirtyfour.multiply(array[received - 1]).subtract(array[received - 2]).add(BigInteger.valueOf(2));
        }
    }
}

Here it is. I hadn't thought using scientific notation for the really large numbers, nice idea. I dunno how to balance accuracy vs practicality. This will continue to print every single number of every single stn from 0 to input. If I were to use scientific notation, I'll probably leave a hundred digits before the 10^x. Probably even more >.< Anyway, it takes prolly 4 secs to get the first 1000, and each stn after that takes more time to print because the number of digits keep increasing. Takes 6 mins for 10000 in my laptop.

        import java.util.*;
        import java.math.*;

        public class FunLoops {
            Scanner in;
            BigInteger [] arr;
            BigInteger two = new BigInteger("2");
            BigInteger thirtyfour = new BigInteger("34");
            int input;

            public FunLoops() {
                in = new Scanner(System.in);
                run();
            }
            public void run(){
                System.out.println("How many square triangular numbers do you want printed?");
                input = in.nextInt();
                arr = new BigInteger[input];
                for(int i=0; i < input; i++){
                    rec(i);
                    System.out.println("Square Triangular Number #" + (i) + ": " + arr[i]);
                }
            }
            public void rec(Integer i){
                long total;
                if(i == 0){
                    arr[0] = BigInteger.valueOf(0);
                }else if(i == 1){
                    arr[1] = BigInteger.valueOf(1);
                }else{
                    arr[i] = thirtyfour.multiply(arr[i-1]).subtract(arr[i-2]).add(two);
                }
            }
        }
Member Avatar for joankim

Wow, mine uses 23 mins for 10000... I guess the scientific notation slows it down a lot. I created another class the only prints the one square, and user can input what # square that is printed. This way, it takes around 5 seconds to find and print square #60000. The max value of BigInteger (only limited by computer's RAM) is reached between 60000 and 70000.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.