mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2015-06-22, 15:40   #12
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

2×5×569 Posts
Default

Quote:
Originally Posted by Drdmitry View Post
The most of platform-specific code appeared in the program because of the need to implement the mulmod function. x64 processors can multiply two 64 bit numbers modulo another 64 bit number just in two basic assembler operations, which is much faster than the standard long arithmetic routine. If one can provide a fast cross-platform implementation of this function that would be great.

In my implementation of mulmod, unfortunately, I did not manage to write it straight in assembler (perhaps because of my poor knowledge of how to add assembler code to a C++ program). I used VC++ intrinsic _mul128 for multiplication and some dirty hack found somewhere on the internet for taking the remainder. Nevertheless this combination worked about ten times faster than if NTL library is used. I did not try GMP but I expect that my mulmod will work significantly faster.

I also used GetTickCount() function from windows.h to measure the time spent by certain procedures. I am sure that this part can easily be made platform independent.
Code:
long long int mulmod(long long int a, long long int b, long long int n) {
    long long int d, dummy; /* d will get a*b mod c */
    asm ("imulq %3\n\t" /* mul a*b -> rdx:rax */
         "idivq %4\n\t" /* (a*b)/c -> quot in rax remainder in rdx */
         :"=a"(dummy), "=&d"(d) /* output */
         :"a"(a), "rm"(b), "rm"(n) /* input */
         :"cc" /* imulq and idivq can set conditions */
        );
    return d;
  }
This is what I use in c for gcc on windows. Will this work in c++? Will this work on linux?
henryzz is offline   Reply With Quote
Old 2015-06-22, 17:15   #13
Antonio
 
Antonio's Avatar
 
"Antonio Key"
Sep 2011
UK

21316 Posts
Default

Quote:
Originally Posted by Antonio View Post
reserving 31730000-31739999
Approx. 10hrs work.
Range complete, no results.

Reserving 31720000-31729999.

Question: is Ctrl-C the only method of exiting the program when it has finished?
Antonio is offline   Reply With Quote
Old 2015-06-22, 17:21   #14
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

2×32×13 Posts
Default

Quote:
Originally Posted by henryzz View Post
Code:
long long int mulmod(long long int a, long long int b, long long int n) {
    long long int d, dummy; /* d will get a*b mod c */
    asm ("imulq %3\n\t" /* mul a*b -> rdx:rax */
         "idivq %4\n\t" /* (a*b)/c -> quot in rax remainder in rdx */
         :"=a"(dummy), "=&d"(d) /* output */
         :"a"(a), "rm"(b), "rm"(n) /* input */
         :"cc" /* imulq and idivq can set conditions */
        );
    return d;
  }
This is what I use in c for gcc on windows. Will this work in c++? Will this work on linux?
It does not work in Visual Studio. (I just remember that VC++ does not support x64 inline assembler). I will try to compile it on Linux machine in the nearest few days.
Drdmitry is offline   Reply With Quote
Old 2015-06-22, 17:29   #15
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

2·32·13 Posts
Default

Quote:
Originally Posted by Antonio View Post
Range complete, no results.

Reserving 31720000-31729999.

Question: is Ctrl-C the only method of exiting the program when it has finished?
Great, thanks. It is interesting to see that cycles are so rare for high numbers.
At the end you can enter any number (or even symbol) to exit. I put that in the code to be sure that the window with the program does not suddenly disappear. That is good for testing the program but probably not for the distributed computing. I will remove that feature and reupload the program again.
Drdmitry is offline   Reply With Quote
Old 2015-06-22, 18:13   #16
ChristianB
 
Apr 2013
Germany

2·32·17 Posts
Default

If you really want to allow some distributed computing with this app you should consider those points too:
  • input and output filenames should be fixed (BOINC renames input and output files for better management)
  • it should be easy to substitute all file open operations through an external library (because the external library will resolve the path)
  • calculate the IOPS/FLOPS that are needed for a certain range (to estimate the runtime on a host where only the benchmark is known)
  • provide some kind of suspend/resume (checkpointing) mechanism (BOINC may switch between applications every X minutes, set by the owner of the host)
This way it can be compiled as a BOINC application and added to an existing BOINC project very easily.
ChristianB is offline   Reply With Quote
Old 2015-06-23, 00:53   #17
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

22·3·29 Posts
Thumbs up

Quote:
Originally Posted by Drdmitry View Post
It does not work in Visual Studio. (I just remember that VC++ does not support x64 inline assembler). I will try to compile it on Linux machine in the nearest few days.
I wrote a quick test using henryzz's gcc code that worked successfully using g++ on an x64 Linux box.
Happy5214 is offline   Reply With Quote
Old 2015-06-23, 04:07   #18
Antonio
 
Antonio's Avatar
 
"Antonio Key"
Sep 2011
UK

21316 Posts
Default

Quote:
Originally Posted by Antonio View Post
Reserving 31720000-31729999.
Only 1 cycle found.
Reserving 31710000-31719999.
Attached Files
File Type: txt output_odd_10e16_31720000-31729999.txt (56 Bytes, 71 views)
Antonio is offline   Reply With Quote
Old 2015-06-23, 10:29   #19
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

2×5×569 Posts
Default

Quote:
Originally Posted by henryzz View Post
Sounds like a good idea.
reserving 31740000-31746032

I am assuming the chance of success is proportional to the time spent rather than the range of n.
Complete no results

reserving 31700000-31709999
henryzz is offline   Reply With Quote
Old 2015-06-23, 11:17   #20
Antonio
 
Antonio's Avatar
 
"Antonio Key"
Sep 2011
UK

32·59 Posts
Default

Quote:
Originally Posted by Antonio View Post
Reserving 31710000-31719999.
Complete, no results.
Reserving 31690000-31699999
Antonio is offline   Reply With Quote
Old 2015-06-23, 15:16   #21
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

23410 Posts
Default

Quote:
Originally Posted by Antonio View Post
Only 1 cycle found.
Reserving 31710000-31719999.
Great, The first pair is found! It is not in the Pat's list, so I'll send it to him with the discoverer name Antonio&Bodyagin. Please let me know if you want to be named otherwise.

Thanks to henryzz, It seems that I have managed to compile the program on Linux. I added the Linux source file to the main archive and also attached it here. The next step will be to translate all the comments there :)

Also I am reserving 1 - 1.
Attached Files
File Type: zip main_linux.zip (7.6 KB, 67 views)
Drdmitry is offline   Reply With Quote
Old 2015-06-23, 15:58   #22
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

31×97 Posts
Default

I got a Linux build. I'll take two ranges.

31670000-31679999
31680000-31689999
RichD is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Aliquot cycles search, the state of the art. Drdmitry Aliquot Sequences 124 2017-07-02 02:48
Search of all even-15-digit Aliquot cycles Drdmitry Aliquot Sequences 25 2016-12-16 15:26
Is a search for aliquot 3-cycles feasible? schickel Aliquot Sequences 7 2013-02-08 01:33
BOINCify Aliquot searching? schickel Aliquot Sequences 23 2011-05-16 23:13
Jan Munch Pedersen's Tables of Aliquot Cycles R. Gerbicz Math 0 2010-07-01 12:30

All times are UTC. The time now is 21:06.

Mon Aug 3 21:06:43 UTC 2020 up 17 days, 16:53, 0 users, load averages: 1.16, 1.26, 1.35

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.