mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-08-23, 14:02   #177
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

749610 Posts
Default

Quote:
Originally Posted by xilman View Post
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?

<snip>
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.
R.D. Silverman is offline   Reply With Quote
Old 2019-08-23, 14:18   #178
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3·17·73 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
bsquared is offline   Reply With Quote
Old 2019-08-23, 14:19   #179
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2D3D16 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
xilman is offline   Reply With Quote
Old 2019-08-23, 14:24   #180
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

1158110 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
xilman is offline   Reply With Quote
Old 2019-08-23, 14:25   #181
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2019-08-23, 14:42   #182
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

37×313 Posts
Default

Quote:
Originally Posted by bsquared View Post
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/
xilman is offline   Reply With Quote
Old 2019-08-23, 14:43   #183
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

521 Posts
Default

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)
Till is offline   Reply With Quote
Old 2019-08-23, 14:45   #184
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3×17×73 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
bsquared is offline   Reply With Quote
Old 2019-08-23, 14:49   #185
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

264758 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
xilman is offline   Reply With Quote
Old 2019-08-23, 15:02   #186
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

72138 Posts
Default

Quote:
Originally Posted by xilman View Post
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:~$
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>
bsquared is offline   Reply With Quote
Old 2019-08-23, 15:35   #187
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2D3D16 Posts
Default

Quote:
Originally Posted by bsquared View Post
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
	sarq	$63, %rcx
	andq	%rdx, %rcx
	leaq	(%rcx,%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:~$
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
	.file	"addmod.c"
	.text
	.p2align 4,,15
	.globl	addmod
	.type	addmod, @function
addmod:
.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!
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring Mersenne numbers paulunderwood Miscellaneous Math 18 2017-08-27 14:56
Factoring Big Numbers In c# ShridharRasal Factoring 10 2008-03-20 17:17
Question about factoring code Peter Nelson Software 9 2005-03-30 18:28
Factoring Fermat Numbers Axel Fox Software 14 2003-07-04 18:57
Questions about SSE2 code and Factoring 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”