Can't stop this integer overflow from giving me a negative number

Posted on 2004-11-29
Last Modified: 2010-03-31
I have a formula below which gives me weights to every other vertex so that i can use dijkstra's algorithm to find the shortest path. The problem is that when i do the calculation some overflow and create negative numbers. I was told if i mod each step it would stop the overflow vs mod the entire value , however neither are working. I'v tried starting with a long then casting to a int still get negatives. If someone could help me that be great!

public void setweights()

        for(int row=0; row < 20 ;row++ )
                   for( int col=0 ; col < 20; col++)
            //  graph[row][col].setDistance(

            int f =   (  ((3751 * to.getRow() + 6539 * graph[row][col].getRow() ) % 1213 )* ((3751 * graph[row][col].getRow() + 6539 * to.getRow()  ) %1213)
                        +  ((4567 * to.getCol() + 9673 * graph[row][col].getCol() ) % 1213) * (( 4567 * graph[row][col].getCol() + 9673 * to.getCol() )%1213)
                       + 1 ;

         //int j = (int) f;


above was trying to mod each part to break it smaller but it gave me wird numbers

the original is as follows i tred modding the entire value

      int f =   (  (3751 * to.getRow() + 6539 * graph[row][col].getRow() ) * (3751 * graph[row][col].getRow() + 6539 * to.getRow()  )
                        +  (4567 * to.getCol() + 9673 * graph[row][col].getCol() )  * ( 4567 * graph[row][col].getCol() + 9673 * to.getCol() )
                       ) %1213
                       + 1 ;

i  was told i had to handle the overflow somehow any help would be much appreciated!
Question by:tyweed420
    LVL 86

    Expert Comment

    The only way to prevent overflow in all circumstances is to use BigInteger
    LVL 1

    Assisted Solution

    The variable "to" is undefined in the code snippet you provide.  What is "to" declared to be?

    Also, in a less programmatic sense, what is the weight function from one vertex of the graph to another?  You can't arbitrarily insert a mod operation into the middle of a function without dramatically changing said function, so it sounds like you are heading down the wrong path altogether.

    As an asside, I seem to recall that dijkstra's algorithm requires that you set the initial value of each node of the graph to "infinity".  We don't have all of your code, but it's possible that some initialization operation iis messing you up.


    Author Comment

    Big integer how do you implement that? is that a long?

    ok, yeah sorry i didn't leave you much info here is the formula.

    Vertex(r1,c1) to
    Vertex(r2,c2) from

     (  (3751 * r1 + 6539 * r2 ) * (3751 * r2 + 6539 * r1 )
                          +  (4567 * c1 + 9673 * c2 )  * ( 4567 * c2 + 9673 * c1 )
                         ) %1213
                         + 1 ;

    "to" is the first vertex
    graph[row][col] are all others

     I initially set the distances which is ok for dikstra's algorithm I just need to do this calculation without it going over the max integer value because it gioves me a negative value. And as we know negative values cause prblems with dijkstras algorithm.
    LVL 86

    Accepted Solution

    LVL 24

    Assisted Solution

    If you only started by replacing     int     by     long
    half your problem was solved already.
    The other half goes when you secure all intermediate results to long.
    LVL 86

    Expert Comment


    Featured Post

    Threat Intelligence Starter Resources

    Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

    Join & Write a Comment

    Suggested Solutions

    Title # Comments Views Activity
    scores100 challenge 3 68
    powerN  challenge 3 36
    json format text only 4 50
    solarwind tftp server 2 19
    This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
    Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
    Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:
    This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.

    754 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    19 Experts available now in Live!

    Get 1:1 Help Now