unsigned long int giving integer overflow

Question

I am trying to create a program in c to solve sudoku puzzles,in which i am trying to store a number equal to 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 in an unsigned long int variable. on compiling with boath gcc and g++ on a 32 bit Ubuntu machine, i am getting an integer overflow error.

please help me storing and using this number, or suggest an alternative.

i am including the whole code for reference.

#include <stdio.h>
#include <stdlib.h>

int main() {
    int sudoku[9][9] = {2, 8, 0, 0, 0, 3, 0, 0, 0, // 0 is used to denote blank
                        4, 7, 0, 0, 8, 6, 0, 9, 1, 0, 0, 5, 0, 9, 0, 2, 3, 0,
                        0, 9, 0, 5, 2, 0, 4, 8, 6, 5, 0, 0, 0, 0, 0, 0, 0, 3,
                        8, 6, 1, 0, 7, 4, 0, 5, 0, 0, 3, 4, 0, 1, 0, 8, 0, 0,
                        7, 5, 0, 8, 3, 0, 0, 2, 4, 0, 0, 0, 6, 0, 0, 0, 7, 9};
    unsigned long int ref[9][9];
    int solved = 0;
    int i, j, k;
    unsigned long int full = 29 * 23 * 19 * 17 * 13 * 11 * 7 * 5 * 3 * 2;
    int key = 0;
    printf("%lu", full);

    for (i = 0; i <= 9; i++) {
        for (j = 0; j <= 9; j++) {
            switch (sudoku[i][j]) {
                case 1:
                    sudoku[i][j] = 2;
                    break;
                case 2:
                    sudoku[i][j] = 3;
                    break;
                case 3:
                    sudoku[i][j] = 5;
                    break;
                case 4:
                    sudoku[i][j] = 7;
                    break;
                case 5:
                    sudoku[i][j] = 11;
                    break;
                case 6:
                    sudoku[i][j] = 13;
                    break;
                case 7:
                    sudoku[i][j] = 17;
                    break;
                case 8:
                    sudoku[i][j] = 19;
                    break;
                case 9:
                    sudoku[i][j] = 23;
                    break;
                case 0:
                    sudoku[i][j] = 29;
                    break;
                default:
                    printf("\n Error in input");
                    break;
            }
        }
    }

    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            ref[i][j] = 29;
        }
    }

    while (!solved) {
        for (i = 0; i < 9; i++) {
            for (j = 0; j < 9; j++) {
                if (sudoku[i][j] != 29) {
                    for (k = 0; k < 9; k++) {
                        if (k != j) {
                            if (ref[i][k] % sudoku[i][j] != 0 &&
                                sudoku[i][k] == 29) {
                                ref[i][k] = ref[i][k] * sudoku[i][j];
                            }
                        }
                    }

                    for (k = 0; k < 9; k++) {
                        if (k != i) {
                            if (ref[k][j] % sudoku[i][j] != 0 &&
                                sudoku[k][j] == 29) {
                                ref[k][j] = ref[k][j] * sudoku[i][j];
                            }
                        }
                    }
                }
            }
        }

        for (i = 0; i < 9; i++) {
            for (j = 0; j < 9; j++) {
                if (ref[i][j] == full / 2 && sudoku[i][j] == 29) {
                    sudoku[i][j] = 2;
                }
                if (ref[i][j] == full / 3 && sudoku[i][j] == 31) {
                    sudoku[i][j] = 3;
                }
                if (ref[i][j] == full / 5 && sudoku[i][j] == 31) {
                    sudoku[i][j] = 5;
                }
                if (ref[i][j] == full / 7 && sudoku[i][j] == 31) {
                    sudoku[i][j] = 7;
                }
                if (ref[i][j] == full / 11 && sudoku[i][j] == 31) {
                    sudoku[i][j] = 11;
                }
                if (ref[i][j] == full / 13 && sudoku[i][j] == 31) {
                    sudoku[i][j] = 13;
                }
                if (ref[i][j] == full / 17 && sudoku[i][j] == 31) {
                    sudoku[i][j] = 17;
                }
                if (ref[i][j] == full / 19 && sudoku[i][j] == 31) {
                    sudoku[i][j] = 19;
                }
                if (ref[i][j] == full / 23 && sudoku[i][j] == 31) {
                    sudoku[i][j] = 23;
                }
            }
        }

        for (i = 0; i < 9; i++) {
            for (j = 0; j < 9; j++) {
                if (sudoku[i][j] == 29) {
                    key = 1;
                }
            }
        }

        if (key == 0) {
            for (i = 0; i < 9; i++) {
                for (j = 0; j < 9; j++) {
                    switch (sudoku[i][j]) {
                        case 2:
                            sudoku[i][j] = 1;
                            break;
                        case 3:
                            sudoku[i][j] = 2;
                            break;
                        case 5:
                            sudoku[i][j] = 3;
                            break;
                        case 7:
                            sudoku[i][j] = 4;
                            break;
                        case 11:
                            sudoku[i][j] = 5;
                            break;
                        case 13:
                            sudoku[i][j] = 6;
                            break;
                        case 17:
                            sudoku[i][j] = 7;
                            break;
                        case 19:
                            sudoku[i][j] = 8;
                            break;
                        case 23:
                            sudoku[i][j] = 9;
                            break;
                    }

                    printf("%d  ", sudoku[i][j]);
                }
                printf("\n");
            }
            solved = 1;
        }

        else {
            key = 0;
        }
    }

    return 0;
}

Best to insure unsigned multiplication with 29u*23*... and go with @Jonatan Goebel, use unsigned long long. — chux
– chux, Commented Aug 4, 2014 at 13:52
Or even uintmax_t to nsure the maximum your system can provide. OTOH, the number you mention is 6469693230, so uint64_t should work as well. — glglgl
– glglgl, Commented Aug 4, 2014 at 13:53

mafso · Accepted Answer · 2014-08-04 14:03:30Z

6

unsigned long int full=29*23*19*17*13*11*7*5*3*2;

Two problems: First, the arithmetical result of the multiplication (6469693230) takes up 33 bits, and an unsigned long may have only 32. An unsigned long long is guaranteed to have at least 64 bit.

Second, and more important: The type of the RHS is int, which can overflow (the term overflow isn't used for unsigned integers, neither by the C standard nor in gcc messages, it's called wrap-around (or truncation, in gcc warnings), which always has well-defined semantics) and in fact does so on most systems. Use

unsigned long long full = 29ull*23*19*17*13*11*7*5*3*2;

instead.

HTH

A final note: Please don't provide that much code unrelated to your actual problem.

edited Aug 4, 2014 at 14:03

answered Aug 4, 2014 at 13:56

mafso

5,5932 gold badges23 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Jongware Over a year ago

+½ for that final note (rounded away from zero)

Prakhar Thakur Over a year ago

Thank you very much for your answer, and more for your suggestion, i will keep that in mind.

4simplicity · Accepted Answer · 2014-08-04 13:58:54Z

0

you can use a wider type, such as long long, or float

answered Aug 4, 2014 at 13:58

4simplicity

316 bronze badges

2 Comments

Serge Ballesta Over a year ago

Avoid float for integer calculations because it can yield accuracy problems.

chux Over a year ago

float typically lack precision for 6469693230. C guarantees minimum 6 significant decimal digits. float xx = 6469693230.0; printf("%.1f\n", xx); --> "6469693440.0"

Collectives™ on Stack Overflow

unsigned long int giving integer overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related