OSDev.org

Posted: **Sun Sep 09, 2007 1:43 pm**

1. I have made a modified recursive factorial function to allow for "partial" factorial like: "10*9*8", it seems to work fine anf yet i think there might be some sort of a bug, allthough im unable to find it.
2. What im trying to do with this code is to use the pfact() function to make calculations like: "5! / 5*4*3" or simular, however the excample im doing, which involves cards, is not working properly.
3. The "cout" printout fails after after 11 iterations and by the it HAS exceeded 32 bits, so i dont think that is the problem.
4. The printf() printout fails after 9 iterations where the border is between less that 32 bit and more that 32 bits, so that probably has something to do with me not using the printf() function right.
5. And finaly i have been unable to make the printf prinout in one line.

Code: Select all

#include <iostream>

#include <stdio.h>

unsigned long long pfact(unsigned long long i,unsigned long long n) {

  if(i == 1) return n;

  return n*pfact(i-1, n-1);

}

int main() {

  for(unsigned long long n = 1; n <= 52; n++) {

    std::cout << n << " -> ";
    std::cout << pfact(n,52)/pfact(n,n) << std::endl;

    printf("%llu -> ",n);
    printf("%llu\n",pfact(n,52)/pfact(n,n));

  }

}

I am aware that the code it self would probebly cause trouble even if it worked as suposed, as it is most likely that the value calculated will exceed 64 bits sooner or later, but still it should not fail this early on.

Thanks

Posted: **Mon Sep 10, 2007 12:28 am**

1) A debugging rule: Subfunctions should always be tested out of context. Yes, you want to use your pfact() function in a cards context, but to test its mathematical correctness you should put it through a full boundary test (0, 1, 2, ULLONG_MAX, those kind of numbers), instead of throwing "real life" values (52) at it.

2) Taking your code verbatim, I do not see any difference between the cout and the printf output.

3) Another debugging rule: Always state expected behaviour and actual behaviour, preferably by copy&pasting output. "Fails after 11 iterations" is a bit inprecise. You mean that the numbers get smaller, or does your code actually fail?

4) "where the border is between less that 32 bit and more that 32 bits" - ?

5) "And finaly i have been unable to make the printf prinout in one line" - you probably mean printf( "%llu -> %llu\n", n, pfact( n, 52 ) / pfact( n, n ) );

That being said, your pfact() looks good. It misbehaves if i == 0 or i > n, but other than that I can't see a problem.

You might want to add the following line to main():

Code: Select all

std::cout << "ull is " << sizeof( unsigned long long ) * 8 << " bits." << std::endl;

Regarding item 2) above, I tested this on a 64bit machine.

Posted: **Mon Sep 10, 2007 9:50 am**

Solar wrote:1) A debugging rule: Subfunctions should always be tested out of context. Yes, you want to use your pfact() function in a cards context, but to test its mathematical correctness you should put it through a full boundary test (0, 1, 2, ULLONG_MAX, those kind of numbers), instead of throwing "real life" values (52) at it.

I have testet the function again and again, however not untill in should exceed 64 bit and fail.

Solar wrote:2) Taking your code verbatim, I do not see any difference between the cout and the printf output.

exactly! Never the less the result the cout and printf prints is different and basicly it look like printf just treats the %llu as 32 bit.

Solar wrote:3) Another debugging rule: Always state expected behaviour and actual behaviour, preferably by copy&pasting output. "Fails after 11 iterations" is a bit inprecise. You mean that the numbers get smaller, or does your code actually fail?

I mean that the result becomes incorrect and to me it might as well fail, but i see your point.

Solar wrote:4) "where the border is between less that 32 bit and more that 32 bits" - ?

Between 2^32-1 and 2^32

Solar wrote:5) "And finaly i have been unable to make the printf prinout in one line" - you probably mean printf( "%llu -> %llu\n", n, pfact( n, 52 ) / pfact( n, n ) );

yes but it doesnt work, the second value just prints zero.

Solar wrote:That being said, your pfact() looks good. It misbehaves if i == 0 or i > n, but other than that I can't see a problem.

i am aware the it is possible to use the functon wrong.

Solar wrote:You might want to add the following line to main():
Code: Select all
std::cout << "ull is " << sizeof( unsigned long long ) * 8 << " bits." << std::endl;
Regarding item 2) above, I tested this on a 64bit machine.

I have done the sizeof() again and again and again, that just isnt the problem.
I have allso tested it on a 64 bit machine, however running 32bit windows so...

this is the output i get:

Code: Select all

1 -> 52
1 -> 52
2 -> 1326
2 -> 1326
3 -> 22100
3 -> 22100
4 -> 270725
4 -> 270725
5 -> 2598960
5 -> 2598960
6 -> 20358520
6 -> 20358520
7 -> 133784560
7 -> 133784560
8 -> 752538150
8 -> 752538150
9 -> 3679075400
9 -> 3679075400
10 -> 15820024220
10 -> 2935122332
11 -> 60403728840
11 -> 274186696
12 -> 13825310247
12 -> 940408359
13 -> 1066226105
13 -> 1066226105
14 -> 7830577
14 -> 7830577
15 -> 5730934
15 -> 5730934
16 -> 27917
16 -> 27917
17 -> 7256
17 -> 7256
18 -> 2584
18 -> 2584
19 -> 75
19 -> 75
20 -> 3
20 -> 3
21 -> 0
21 -> 0
22 -> 0
22 -> 0
23 -> 0
23 -> 0
24 -> 1
24 -> 1
25 -> 1
25 -> 1
26 -> 0
26 -> 0
27 -> 0
27 -> 0
28 -> 0
28 -> 0
29 -> 0
29 -> 0
30 -> 1
30 -> 1
31 -> 3
31 -> 3
32 -> 1
32 -> 1
33 -> 4
33 -> 4
34 -> 1
34 -> 1
35 -> 2
35 -> 2
36 -> 0
36 -> 0
37 -> 3
37 -> 3
38 -> 1
38 -> 1
39 -> 7
39 -> 7
40 -> 0
40 -> 0
41 -> 0
41 -> 0
42 -> 1
42 -> 1
43 -> 1
43 -> 1
44 -> 3
44 -> 3
45 -> 0
45 -> 0
46 -> 9
46 -> 9
47 -> 0
47 -> 0
48 -> 0
48 -> 0
49 -> 1
49 -> 1
50 -> 0
50 -> 0
51 -> 0
51 -> 0
52 -> 1
52 -> 1

as for the expected output, it is some pretty large numbers.

Posted: **Mon Sep 10, 2007 10:09 am**

an unsigned long long isn't large enough to hold 52*51*..*2*1. You have some 20 decimal digits at your disposal, so when you use more than 20 components, you already overrun that limit. Find a smarter way to calculate these _huge_ numbers since you need several hundred bits to store 52 faculty

However, it does not explain why the output never surpasses the 4 billion limit of a 32-bit number

Posted: **Mon Sep 10, 2007 10:18 am**

Combuster wrote:an unsigned long long isn't large enough to hold 52*51*..*2*1. You have some 20 decimal digits at your disposal, so when you use more than 20 components, you already overrun that limit. Find a smarter way to calculate these _huge_ numbers since you need several hundred bits to store 52 faculty

I am aware of that, and i didnt expect it to run all the way through the program without errors and undefined behaviour, but neither did i expect it to "fail" this early.

The thing is that at some point the result should actually begin to get smaller.
52! / 52! == 1

i actually expected the pfact() function to hit its limitation before that, however the windows calculator suggest that an unsigned long long is actually big enough to hold the result given by pfact():
52! == 0x8A B2 00 00 00 00 00 00 == 64 bits
however it is allways possible that the windows calculator has made an error, but i am deffinently not gonna do the math by hand

edit:

Code: Select all

#include <iostream>
#include <stdio.h>
unsigned long long pfact(unsigned long long i,unsigned long long n) {
  if(i == 1) return n;
  return n*pfact(i-1,n-1);
}
int main() {
  std::cout << std::hex << pfact(52,52) << std::endl;
  printf("%llu\n", pfact(52, 52));
}

output std::cout == 0x8a b2 00 00 00 00 00 00
output printf() == 0

1. The cout printout suggest that the result is actually not to large to be hold in a 64 bit uint.
2. I have not made the printf() prinout in hex, as i do not know how, but still it suggests that something is terible wrong.

Posted: **Mon Sep 10, 2007 6:28 pm**

I think the windows calculator uses long doubles, which can go up to 80 bits - iirc it works up to something like +/- 3.4E+4936.

Posted: **Mon Sep 10, 2007 6:49 pm**

well, the decimal part probably does, but when showing values in either hex or binary (probably oct allso) it can show max 2^64-1, eg. it seem like its using ulls after all.

Still the interesting part is that seemingly, assuming combuster is right, 52! cant be hold in a 64 bit unsigned var, and yet it seems i get the correct result.

Posted: **Mon Sep 10, 2007 7:59 pm**

52! = 8.0658175170943878571660636856404e+67.

The only way that can be stored accurately is in a long double...

when showing values in either hex or binary (probably oct allso) it can show max 2^64-1, eg. it seem like its using ulls after all.

I think for the decimal mode it uses long doubles, because it needs the precision, but for hexadecimal mode (with QWord on) it uses unsigned long longs, because there is no floating point precision required.

Posted: **Mon Sep 10, 2007 8:53 pm**

ok, but please give a clear answer: can 52! be stored in an ull?
Why is it that, if that is not the case, the calculator act very specific like:
in decimal mode i calculate 52!, no problems. i switch to hex mode and still no problems, but when doing the same with, fx. 64^2, the switch to hex will result only in a zero value.

Posted: **Mon Sep 10, 2007 9:31 pm**

Basically, there is no way to print out a long double as a hexadecimal value.

There is a way to print out a long double as a decimal value.

So it prints what it can.

Posted: **Tue Sep 11, 2007 12:29 am**

like I said, before you need several hundred significant binary digits to store the result. My mental calculator tells me that I need some 220 bits to store it as an integer, and some 200 to store it as a floating point number.

Btw, you can much easier convert a floating point number to hex than to decimal - just like a normal int is easier converted to hex.

Posted: **Tue Sep 11, 2007 12:30 am**

Zacariaz wrote:ok, but please give a clear answer: can 52! be stored in an ull?

No.

Why is it that, if that is not the case, the calculator act very specific like...

Because a calculator doesn't use ull internally.

As for the difference in output, I get:

Code: Select all

1 -> 52
1 -> 52
2 -> 1326
2 -> 1326
3 -> 22100
3 -> 22100
4 -> 270725
4 -> 270725
5 -> 2598960
5 -> 2598960
6 -> 20358520
6 -> 20358520
7 -> 133784560
7 -> 133784560
8 -> 752538150
8 -> 752538150
9 -> 3679075400
9 -> 3679075400
10 -> 15820024220
10 -> 15820024220
11 -> 60403728840
11 -> 60403728840
12 -> 13825310247
12 -> 13825310247
13 -> 1066226105
13 -> 1066226105
14 -> 7830577
14 -> 7830577
15 -> 5730934
15 -> 5730934
16 -> 27917
16 -> 27917
17 -> 7256
17 -> 7256
18 -> 2584
18 -> 2584
19 -> 75
19 -> 75
...

Machine is sparc-sun-solaris2.10, sizeof( unsigned long long ) is 8, GCC version is 4.0.1. And the printf() line I gave works fine for me.

Posted: **Tue Sep 11, 2007 12:58 am**

i run windows and get:

1 -> 52
1 -> 52
2 -> 1326
2 -> 1326
3 -> 22100
3 -> 22100
4 -> 270725
4 -> 270725
5 -> 2598960
5 -> 2598960
6 -> 20358520
6 -> 20358520
7 -> 133784560
7 -> 133784560
8 -> 752538150
8 -> 752538150
9 -> 3679075400
9 -> 3679075400
10 -> 15820024220
10 -> 15820024220
11 -> 60403728840
11 -> 60403728840
12 -> 13825310247
12 -> 13825310247
13 -> 1066226105
13 -> 1066226105
14 -> 7830577
14 -> 7830577
15 -> 5730934
15 -> 5730934
16 -> 27917
16 -> 27917
17 -> 7256
17 -> 7256
18 -> 2584
18 -> 2584
19 -> 75
19 -> 75

so windows is not the problem. do you compile with gcc or mingw? %llu is only supported in gcc without the -mwindows or -mno-cygwin ..

Posted: **Tue Sep 11, 2007 1:10 am**

Combuster wrote:Btw, you can much easier convert a floating point number to hex than to decimal - just like a normal int is easier converted to hex.

Sorry, I read somewhere that it wasn't possible...

like I said, before you need several hundred significant binary digits to store the result. My mental calculator tells me that I need some 220 bits to store it as an integer, and some 200 to store it as a floating point number.

I didn't see that reply, oops. I do know though that a long double can hold a massive amount of data (80-bit double precision).

Posted: **Tue Sep 11, 2007 1:31 am**

...at the loss of precision. IIRC, 32-bit float offers 6 digits of precision, a 64-bit float 15 digits, and a 80-bit float about 19 digits. Means, you get that many leading digits right, but don't count on the rest being precise.

(The precision of a long double in your environment can be tested for by evaluating LDBL_DIG in <float.h>.)

OSDev.org

severel problems (c/c++)

severel problems (c/c++)