mersenneforum.org Some code for factoring numbers up to 2^63
 Register FAQ Search Today's Posts Mark Forums Read

2019-08-23, 14:02   #177
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

749610 Posts

Quote:
 Originally Posted by xilman The conditional arithmetic may compile to mis-predicted branches on some architectures and cause an overall slowdown. Sometimes it is faster to mask, shift and add/subtract. E.g. Code: long addmod(long x, long y, long n) { long r0 = x-y; return r0 + (n & ((n-r0) >> (sizeof (long) * sizeof (char))); } /* Check this carefully, I typed it in but have not fed it into a compiler !!! */ Have you experimented along these lines?
This code can't be correct. You are right shifting by 256 bits! [or perhaps more
if sizeof(long) != 32].

BTW, it is very bad style to use 'long'. One should either user int64_t or int32_t.

2019-08-23, 14:18   #178
bsquared

"Ben"
Feb 2007

3·17·73 Posts

Quote:
 Originally Posted by R.D. Silverman This code can't be correct. You are right shifting by 256 bits! [or perhaps more if sizeof(long) != 32]. BTW, it is very bad style to use 'long'. One should either user int64_t or int32_t.
sizeof() returns the size in bytes. As written, the shift would be by 4 (in C, where long's are usually 4 bytes). I haven't studied the code snippet enough to know if this is correct, but it isn't obviously wrong.

The context, however, is Java. There, long's are 8 bytes and int64_t's don't exist. Also not sure if Java has a "sizeof" equivalent.

2019-08-23, 14:19   #179
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2D3D16 Posts

Quote:
 Originally Posted by R.D. Silverman This code can't be correct. You are right shifting by 256 bits! [or perhaps more if sizeof(long) != 32]. BTW, it is very bad style to use 'long'. One should either user int64_t or int32_t.
This post can't be correct. sizeof() returns the number of chars, not the number of bits.

Nonetheless, my code is indeed incorrect because sizeof(char) == 1. It should have read sizeof(long) << 3.

As for style, I completely agree. However, the original used long so, out of politeness, I did the same.

Last fiddled with by xilman on 2019-08-23 at 14:21

2019-08-23, 14:24   #180
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

1158110 Posts

Quote:
 Originally Posted by bsquared There, long's are 8 bytes and int64_t's don't exist. Also not sure if Java has a "sizeof" equivalent.
Don't know, don't care. If the language specifies that longs are invariably 64 bits long it is safe to use that explicit numeric value.

2019-08-23, 14:25   #181
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts

Quote:
 Originally Posted by bsquared sizeof() returns the size in bytes. As written, the shift would be by 4 (in C, where long's are usually 4 bytes). I haven't studied the code snippet enough to know if this is correct, but it isn't obviously wrong. The context, however, is Java. There, long's are 8 bytes and int64_t's don't exist. Also not sure if Java has a "sizeof" equivalent.
Got it.

2019-08-23, 14:42   #182
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

37×313 Posts

Quote:
 Originally Posted by bsquared As written, the shift would be by 4 (in C, where long's are usually 4 bytes).
Toto, I've a feeling we're not in Kansas any more.
Code:
pcl@thoth:~$cat long.c #include <stdlib.h> #include <stdio.h> extern int main () { printf ("sizeof (long) = %lu\n",sizeof(long)); return EXIT_SUCCESS; } pcl@thoth:~$ gcc --pedantic -o long long.c
pcl@thoth:~$./long sizeof (long) = 8 pcl@thoth:~$

Last fiddled with by xilman on 2019-08-23 at 14:44 Reason: s/anymore/any more/

 2019-08-23, 14:43 #183 Till     "Tilman Neumann" Jan 2016 Germany 521 Posts In Java, there is a wrapper class for each primitive type, say wrapper class Long for primitive type long. Each wrapper class has a SIZE constant which gives the size of the data type in bits, and since Java 1.8 a BYTES constant that does the same in bytes. The long size is not invariably 8 bytes, otherwise there would be no reason to have those constants. On the other hand, exceptions seem to be very rare. (I don't know any, but that doesn't mean much)
2019-08-23, 14:45   #184
bsquared

"Ben"
Feb 2007

3×17×73 Posts

Quote:
 Originally Posted by xilman It should have read sizeof(long) << 3.
Your code is clever and I understand its intent, but it seems to rely on the compiler to "do the right thing". Using gcc 7.3.0 I get a warning: warning: right shift count >= width of type [-Wshift-count-overflow]. So, will it shift in all 1's as its supposed to or will it just ignore the shift? It is probably implementation specific.

I was trying to get the compiler to emit cmov instructions which are fast and branch-free (its what the assembler submod does). I haven't tested recently to see if they are clever enough to do so, but one can hope.

2019-08-23, 14:49   #185
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

264758 Posts

Quote:
 Originally Posted by bsquared Your code is clever and I understand its intent, but it seems to rely on the compiler to "do the right thing". Using gcc 7.3.0 I get a warning: warning: right shift count >= width of type [-Wshift-count-overflow]. So, will it shift in all 1's as its supposed to or will it just ignore the shift? It is probably implementation specific. I was trying to get the compiler to emit cmov instructions which are fast and branch-free (its what the assembler submod does). I haven't tested recently to see if they are clever enough to do so, but one can hope.
Obvious fix: subtract 1 from the shift count. All the constants will be optimized away and you'll be left with 31 or 63 or whatever is appropriate.

I did warn you that I typed it in off the top of my head and didn't check it. Trust but verify!

Last fiddled with by xilman on 2019-08-23 at 14:50 Reason: Fix tyops. It's just too darned hot to think properly.

2019-08-23, 15:02   #186
bsquared

"Ben"
Feb 2007

72138 Posts

Quote:
 Originally Posted by xilman Toto, I've a feeling we're not in Kansas any more. Code: pcl@thoth:~$cat long.c #include #include extern int main () { printf ("sizeof (long) = %lu\n",sizeof(long)); return EXIT_SUCCESS; } pcl@thoth:~$ gcc --pedantic -o long long.c pcl@thoth:~$./long sizeof (long) = 8 pcl@thoth:~$
Maybe "usually" was too strong a word, but: https://docs.microsoft.com/en-us/cpp...s?view=vs-2019

Code:
PS H:\src\c\long\Project1\Debug> .\long.exe
sizeof (long) = 4
PS H:\src\c\long\Project1\Debug>

2019-08-23, 15:35   #187
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2D3D16 Posts

Quote:
 Originally Posted by bsquared Your code is clever and I understand its intent, but it seems to rely on the compiler to "do the right thing". Using gcc 7.3.0 I get a warning: warning: right shift count >= width of type [-Wshift-count-overflow]. So, will it shift in all 1's as its supposed to or will it just ignore the shift? It is probably implementation specific. I was trying to get the compiler to emit cmov instructions which are fast and branch-free (its what the assembler submod does). I haven't tested recently to see if they are clever enough to do so, but one can hope.
Code:
pcl@thoth:~$cat addmod.c long addmod(long x, long y, long n) { long r0 = x-y; return r0 + (n & ((n-r0) >> 63)); } pcl@thoth:~$ gcc -O3 -S addmod.c
pcl@thoth:~cat addmod.s .file "addmod.c" .text .p2align 4,,15 .globl addmod .type addmod, @function addmod: .LFB0: .cfi_startproc subq %rsi, %rdi movq %rdx, %rcx subq %rdi, %rcx sarq63, %rcx
andq	%rdx, %rcx
leaq	(%rcx,%rdi), %rax
ret
.cfi_endproc
.LFE0:
.ident	"GCC: (Ubuntu 8.3.0-6ubuntu1) 8.3.0"
.section	.note.GNU-stack,"",@progbits
pcl@thoth:~$This variant trades a movq for a subq. I've no idea whether it makes any difference to the performance. Code: pcl@thoth:~$ cat addmod.c
long addmod(long x, long y, long n) {
return (x-y)+(n & ((n+y-x) >> 63));
}
pcl@thoth:~$gcc -O3 -S addmod.c pcl@thoth:~$ cat addmod.s
.text
.p2align 4,,15
.LFB0:
.cfi_startproc
leaq	(%rsi,%rdx), %rax
subq	%rdi, %rax
subq	%rsi, %rdi
sarq	$63, %rax andq %rdx, %rax addq %rdi, %rax ret .cfi_endproc .LFE0: .size addmod, .-addmod .ident "GCC: (Ubuntu 8.3.0-6ubuntu1) 8.3.0" .section .note.GNU-stack,"",@progbits pcl@thoth:~$
The take-home message is to experiment and see which works best on your hardware.

Experimenting with in-line directives or macros is highly recommended!

 Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Miscellaneous Math 18 2017-08-27 14:56 ShridharRasal Factoring 10 2008-03-20 17:17 Peter Nelson Software 9 2005-03-30 18:28 Axel Fox Software 14 2003-07-04 18:57 Joe O Software 2 2002-09-13 23:39

All times are UTC. The time now is 20:19.

Fri Dec 2 20:19:50 UTC 2022 up 106 days, 17:48, 0 users, load averages: 1.65, 1.42, 1.33