Operator * and + produces wrong result in numeric mars
I am trying to compute a number that produces a long Collatz sequence. But here's a weird problem. 3n+1
becomes 38654705674
when n
equal to 3. I see no error. here is the complete code:
/* 6.c -- calculates Longest Collatz sequence */
#include <stdio.h>
long long get_collatz_length(long long);
int main(void)
{
long long i;
long long current, current_count, count;
current_count = 1;
current = 1;
for(i=2;i<1000000;i++)
{
// works fine when i is 2 the next line take eternity when i is 3;
count = get_collatz_length(i);
if(current_count <= count)
{
current = i;
current_count = count;
}
}
printf("%lld %lld\n", current, current_count);
return 0;
}
long long get_collatz_length(long long num)
{
long long count;
count = 1;
while(num != 1)
{
printf("%lld\n", num);
if(num%2)
{
num = num*3+1; // here it is;
}
else
{
num/=2;
}
count++;
}
puts("");
return count;
}
source to share
It seems to be a bug in the compiler that does dmc
not handle the type correctly long long
. Here's a narrowed down test case:
#include <stdio.h>
int main(void)
{
long long num = 3LL;
/*printf("%lld\n", num);*/
num = num * 3LL;
char *t = (char *) #
for (int i = 0; i < 8; i++)
printf("%x\t", t[i]);
putchar('\n');
/*printf("%lld\n", num);*/
return 0;
}
It produces (a bit endian, so 0x900000009
== 38 654 705 673
):
9 0 0 0 9 0 0 0
From disassembly, it looks like it stores a 64 bit integer as two 32 bit registers:
.data:0x000000be 6bd203 imul edx,edx,0x3
.data:0x000000c1 6bc803 imul ecx,eax,0x3
.data:0x000000c4 03ca add ecx,edx
.data:0x000000c6 ba03000000 mov edx,0x3
.data:0x000000cb f7e2 mul edx
.data:0x000000cd 03d1 add edx,ecx
.data:0x000000cf 31c0 xor eax,eax
I tested it further with a help objconv
that just confirms my original diagnosis:
#include <stdio.h>
void mul(void)
{
long long a;
long long c;
a = 5LL;
c = a * 3LL;
printf("%llx\n", c);
}
int main(void)
{
mul();
return 0;
}
disassembly (separate section):
>objconv.exe -fmasm ..\dm\bin\check.obj
_mul PROC NEAR
mov eax, 5 ; 0000 _ B8, 00000005
cdq ; 0005 _ 99
imul edx, edx, 3 ; 0006 _ 6B. D2, 03
imul ecx, eax, 3 ; 0009 _ 6B. C8, 03
add ecx, edx ; 000C _ 03. CA
mov edx, 3 ; 000E _ BA, 00000003
mul edx ; 0013 _ F7. E2
add edx, ecx ; 0015 _ 03. D1
push edx ; 0017 _ 52
push eax ; 0018 _ 50
push offset FLAT:?_001 ; 0019 _ 68, 00000000(segrel)
call _printf ; 001E _ E8, 00000000(rel)
add esp, 12 ; 0023 _ 83. C4, 0C
ret ; 0026 _ C3
_mul ENDP
Note that mul edx
works implicitly on eax
. The result is stored in both registers, the higher part (in this case 0
) stored in edx
, and the lower part in eax
.
source to share