mersenneforum.org Sociable Numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2014-12-09, 16:10 #34 EdH     "Ed Hall" Dec 2009 Adirondack Mtns C8E16 Posts Hi Drdmitry, My current program only checks up to 4 cycles, and only checks 0 mod 4 and 0 mod 3 even numbers, since I understood you to have covered the others. I'm working at 2*10^13 right now and my fastest machines are checking 1e6 blocks in ~11 seconds, per core. Those machines are Core 2 @ ~3GHz. If you'd like to provide a program, that would be great. It sounds like yours is much faster than what I put together. I changed the 4 cycle limit to 100 in my program and it didn't return from its first 1e6 block for 7 hours! Of course, I didn't do anything extra for breaking out early, so some of the sequences ran up to the full 100 iterations. I've been dabbling recently in the CUDA area to see if I can make something a bit faster, but the programming progress is slow. Ed
2014-12-10, 13:07   #35
Drdmitry

Nov 2011

233 Posts

Here is my program. I'm afraid I can only provide a 64-bit version of it. I had a 32-bit version sometimes ago, but then I had to use a large integer arithmetics. That was about 10 times slower than the current program.
The algorithm now is pretty close to that explained in D. Moews, P. Moews paper. It searches for all cycles where the element preceding the largest element lies in the given range. For optimization reasons it skips all odd numbers less than 10e14 (since they are already been searched). Also it skips all cycles with the smallest elements less than 10e9. If there are new cycles with this property then (I guess) the largest element of such cycle must be out of the range 2^61 supported by the program.
I also put a source code here. It is VC++ and x64 specific. However with some efforts it can be adopted to other platforms.
Attached Files
 aliquot.exe (248.0 KB, 75 views) aliquot.zip (3.2 KB, 88 views)

 2014-12-10, 15:00 #36 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 1100100011102 Posts Thanks! I don't have any Windows machines operating right now, but I will look over the source when I can get a chance. This might add in some interest for some others who weren't ready to program it themselves.
2014-12-11, 20:18   #37
EdH

"Ed Hall"
Dec 2009

2×1,607 Posts

Quote:
 Originally Posted by MichelMarcus Jamais 2 sans 3 ?
Il est vrai! Merci, Michel (and others)!
Code:
20770607674232 = 2E3.13.47.28097.151237
22064204391688 = 2E3.19.37.3923222687
22660534251512 = 2E3.19.367.419.969497
22293149012488 = 2E3.41.283.461.520967
I am wondering, though, if I should wait to see if more show up before bothering David Moews any more with individual finds, since I am running an on-going project and he does a lot of renumbering for each find. On the one hand, I like to see them in his list and letting him know, keeps the list current, but I don't like causing him the extra work on too frequent a basis. An occasional list, if any, might alleviate some of his work. I intend to ask him via email. Of course, the "in"frequency of finds might alleviate that concern...

2014-12-12, 20:52   #38
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT)

130528 Posts

Quote:
 Originally Posted by EdH Thanks! I don't have any Windows machines operating right now, but I will look over the source when I can get a chance. This might add in some interest for some others who weren't ready to program it themselves.
wine

2014-12-12, 23:33   #39
EdH

"Ed Hall"
Dec 2009

2·1,607 Posts

Quote:
 Originally Posted by henryzz wine
as opposed to wine or whine...

I never think of that anymore. I'm not sure why. I do think of virtual machines, but I recently had to reinstall the OS on my main machine and haven't gotten VirtualBox running yet.

I did install wine and the program seems to run very comparable to my perl version, except that it is searching for cycles much greater than my 4 cycle limit.

I will have to see how I can incorporate this new program into my existing machine network. That and seeing if I can compile it on linux. I tried to compile the c++ code and I don't have the proper intrin.h file apparently. In fact, I have many ##intrin.h files, but none that are just intrin.h. Is that a Windows OS specific header of some sort?

Thanks to all!

2014-12-13, 12:49   #40
Drdmitry

Nov 2011

233 Posts

Quote:
 Originally Posted by EdH as opposed to wine or whine... I will have to see how I can incorporate this new program into my existing machine network. That and seeing if I can compile it on linux. I tried to compile the c++ code and I don't have the proper intrin.h file apparently. In fact, I have many ##intrin.h files, but none that are just intrin.h. Is that a Windows OS specific header of some sort?
intrin.h contains all intrinsics available in Visual Studio. I used it only for one function _mul128 which multiplies two 64-bit numbers and returns 128-bit result.
Actually to adopt the program to another platform one just needs to rewrite mulmod function which simply multiplies two 64-bit numbers modulo another 64-bit number. The problem is that X64 processors can do that in just two commands. However C++, as well as the most of other high level languages, does not support this feature. You firstly need to implement 128-bit arithmetic which makes program significantly slower. So _mul128 replaces one of the x64 commands. Another command is encoded directly in machine codes (I copied that trick from some forum on the internet).

2014-12-13, 14:30   #41
EdH

"Ed Hall"
Dec 2009

2·1,607 Posts

Quote:
 Originally Posted by Drdmitry intrin.h contains all intrinsics available in Visual Studio. I used it only for one function _mul128 which multiplies two 64-bit numbers and returns 128-bit result. Actually to adopt the program to another platform one just needs to rewrite mulmod function which simply multiplies two 64-bit numbers modulo another 64-bit number. The problem is that X64 processors can do that in just two commands. However C++, as well as the most of other high level languages, does not support this feature. You firstly need to implement 128-bit arithmetic which makes program significantly slower. So _mul128 replaces one of the x64 commands. Another command is encoded directly in machine codes (I copied that trick from some forum on the internet).
Thanks! I will look into this more. It sounds like it might also solve my trouble I have with trying to program a Miller-Rabin routine into my CUDA stuff recently - never did get that working.

 2014-12-13, 22:45 #42 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 2×1,607 Posts I seem to have __int128 available to me via gcc in linux, so I started rewriting your code. I didn't have too much time and then I thought, if I'm going to the bother, maybe I should just go back to the Moews' paper, especially since I don't have an understanding of inline assembly and my assembly knowledge is too old to make much use of for anything like this. This will be a good way to exercise the little knowledge I have and hopefully expand it. Thanks, again...
 2014-12-22, 02:14 #43 EdH     "Ed Hall" Dec 2009 Adirondack Mtns C8E16 Posts Yet, another: Code: 23255440525768 = 2E3.11.23.97.137.864613 27258491133752 = 2E3.23.277.967.553067 26321320852168 = 2E3.17.107.1201.1506059 26466564087032 = 2E3.521.28879.219881 Thanks, all...
2015-01-09, 11:58   #44
Drdmitry

Nov 2011

233 Posts

Unfortunately I do not have enough computer power to do a exhaustive search of aliquot cycles in a reasonable range. So I played a little bit with my program to see what can be done with it relatively quickly.
Firstly if the search is restricted to odd numbers only then it goes much faster: It took about 12.3 secs per 10^8 on one core of my laptop - about 100 times faster than for even numbers. I checked all odd numbers between 10e13 and 12e13.
Then I also checked all 15-digit odd numbers of the form
3a1 * 5a2 * ... * 29a9 * n
with n up to around 6e7. I am still running a program to extend the full search for n up to about 12e8. However now as the new term starts I will not be able to pay too much attention on it and I am not sure that I will actually complete the search.
I did also some other funny checks. No new cycles of length more than two were found, I'm afraid. On the other hand 137 new amicable pairs, not presented in Pedersen's tables were found. I attach the file with them here.
I also found an inaccuracy in Mathworld article about amicable pairs. It is said that the smallest known pair with elements coprime to 6 has 32 digits. However in Pedersens list there is a pair
Quote:
 5480828320492525=5^2*7^2*11*13*19*31*17*23*103*1319 5786392931193875=5^3*7*11*13*19*31*37*43*61*809
which has only 16 digits - twice less.
Attached Files
 newfound_druz.txt (14.7 KB, 86 views)

 Similar Threads Thread Thread Starter Forum Replies Last Post devarajkandadai Number Theory Discussion Group 0 2017-07-09 05:07 henryzz Math 2 2008-04-29 02:05 T.Rex Math 4 2005-05-07 08:25

All times are UTC. The time now is 17:45.

Fri Jul 3 17:45:24 UTC 2020 up 100 days, 15:18, 2 users, load averages: 1.72, 1.64, 1.63