kangaroo-wild using precomputed and selected DP

I'm curious about how quickly a regular PC with standard RAM and no GPU can find a key in a smaller range like 2^74 2^75. So, I went ahead and created my own version of the kangaroo algorithm: https://github.com/arulbero/kangaroo-wild On my laptop (Alder Lake 12th Gen Intel(R) Core(TM) i7-12700H), it takes roughly 3 seconds for each key. It's a bit quicker if I search for multiple keys at once. The program can also find keys in higher ranges (like 2^77 2^78 or 2^80 2^81) using the same database. Database size: 6GB.

hi there arulbero, the 2nd file is not available anymore, could you help out, thanks for this another master piece

Now it should work.

./kangaroo_wild extend 037e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc 79 80 [PARAMS] V2 loaded: local=12 jump=9 hist=4 esc=128 mult=2000 min_dp=1 trunc=11 [PARAMS] GLOBAL_BITS=16 RANGE=74-75 DIST_BYTES=8 TRUNC_BITS=11 [PARAMS] scored_target_dp=268435456 seed=42 local_buf1=64 [PARAMS] q_hat=0.428733 R_factor=1.1 N_sel=536870912 [JUMP_TABLE] target_dp=268435456 gap=3.52e+13 opt=137438953472 (2^37.0) ==================================================== [DB] 4194304.00 KB | 536870912 entries (disk: 8 B/entry, dist:8, trunc:11) [FP] Fingerprints: 2097152.00 KB (536870912 entries) [BO] Bucket offsets: 16384.00 KB (HASH_INDEX_BITS=22, u32) ==================================================== --- KANGAROO WILD --- [CONFIG] Range: 2^74 - 2^75 | GLOBAL_BITS: 16 | DIST_BYTES: 8 | TRUNC_BITS: 11 [CONFIG] Workers: 60 | Batch: 20 | C: 1200 | VITA: 4194304 [EXTEND] Range 2^79 - 2^80 | DB 2^74 - 2^75 | 32 partitions [KEY 1/1] Searching (extend 2^79-2^80, 32 parts): 037e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc [EXTEND 1/1] 140.2M steps | 46.5M/s | 3s elapsed [EXTEND 1/1] 313.2M steps | 52.0M/s | 6s elapsed [EXTEND 1/1] 523.3M steps | 58.0M/s | 9s elapsed [EXTEND 1/1] 789.1M steps | 65.6M/s | 12s elapsed [EXTEND 1/1] 1143.2M steps | 76.1M/s | 15s elapsed [EXTEND 1/1] 1609.9M steps | 89.3M/s | 18s elapsed [EXTEND 1/1] 2126.0M steps | 101.1M/s | 21s elapsed [EXTEND 1/1] 2667.9M steps | 111.0M/s | 24s elapsed [!!!] KEY FOUND (f2 m1/1 delta=710 partition=26): 0x61a5c66dcc11b5ad180 [SOLVED 1/1] Key: 0xea1a5c66dcc11b5ad180 (part 26) | Steps: 2862.9M | Time: 25.133s ============================================================            STEP ACCOUNTING REPORT ============================================================  Total steps:               2862.87M ------------------------------------------------------------  BREAKDOWN:    life_limit rsp:                0    buf1 (cycle) rsp:              2    escape rsp:                    0    escape jumps:            6866748    avg life at rsp:         1780856 ------------------------------------------------------------  DP STATS:    DP global hits:            43611    DP filtered (k):               0    DP saved:                      0  WILD STATS:    DP checked vs DB:          43611    DB matches:                    1 ============================================================ [!!!] PRIVATE KEY: 0xea1a5c66dcc11b5ad180 wow did not expected this one, thought on extend parallel and or do we get saved dps or tames or wilds in this one or is it needed just to ask, what to edit for this besides the 23 you did, and or threads or batch, after compiling the file it does not take in the -b and or -w just keeps the settings from the file, no problem btw,

I removed the -w - b options because the program runs slower. I just update the program and the flag of compiler. I'm working on a new version of the db, time to retrieve a key: -25% On my pc these are the results with the new database: - sequential search :  2.2 seconds for each key (16 workers, 20 batch_k, 74-75 bit range) - parallel search : 1.1 seconds for each key (16 workers, 60 batch_k, 74-75 bit range) - parallel search: 46 seconds for each key (16 workers, 60 batch_k, 80-81 bit range) On AWS (c8id.metal-48xl instance, 96 core 3.9 GHz, 2 thread for each core): - sequential search: 0.46 seconds for each key (192 workers, 20 batch_k, 74-75 bit range) - parallel search: 0.072 seconds for each key (192 workers, 60 batch_k, 74-75 bit range) - parallel search: 6 seconds for each key (192 workers, 60 batch_k, 80-81 bit range) - parallel search: about 45 seconds for each key (192 workers, 60 batch_k, 84-85 bit range)

can't wait to test that one to, thanks for explaining showing the details, what would be the best setting to setup this code for the 135th puzzle,

Git link not work, some one share new link    or upload full git + compile file use https://gofile.io @arulbero why deleted git ?

This program is only for the short range 2^74-2^75 and for a few bits more (like 80 or 84). It doesn't make sense trying to resolve the 135th puzzle with a cpu, gpus are way more fast.   Only in this short range "cpu with the database of the precomputed dp" is like (more or less) to "a gpu" At the moment the program can search to 2**74 * (2**12) = 2**74 * 4096 = 2**86 - 2**87 range: if you want to search in the 2**100 - 2**101 range: 26 means that it takes 2^26 times more than time to 2^74-75 range, let's say it takes 1s on 2^74-75, are you sure you want to wait 2^26 seconds = 2 years? I didn't delete anything, the link is ok. ********************************************************************************* EDIT: Database updated! Enjoy the speedup!

i was share my screenshot https://pikwy.com/web/69b16f7b158aa71c200dd2ad  . you can see "404 this is not the page you are looking for" what happen i cant see git someone help to download this git files https://github.com/arulbero/kangaroo-wild thankyou

You are right, there is a problem with my github account, I uploaded the code + DB files here:   https://gofile.io/d/9af4a6a1-ae82-43a7-9cf1-a1374e39e040 To compile:   gcc -O3 -march=native -falign-functions=32 -falign-loops=32 kangaroo_wild.c G_stub.c -o kangaroo_wild -pthread -lm -flto

Indeed , your version is faster than keyhunt bsgs . Puzzle 75 - Time: 0.216s Puzzle 80 - Time: 1.016s Puzzle 85 - Time: 118.365s

Thanks. Note: the kangaroo algorithm is probabilistic, to have a real measure you need to test at least 1000 keys to get "a mean time". And to have a better time with different keys I think it is better 384 x 60 instead of 384 x 20.  118s is too much for 85 bit, my average time is 65s (and 1s for 80 bit is too low), you should get under 40s (mean time) for 85 bit, and median time usually is even better.   For 80 bit you should get around 3s (or maybe "your" cores are faster than mine?) 85 bit should be about 2^5 = 32 times 80 bit, not 120 times. This is the readme file:

Ok, I've done some tests, here are my results.  Workers: 384 | Batch: 60

30/50 keys -> too much variance, if you do these tests again probably you will get very different results. You should get around 3s for 80 bit and around 50s (maybe, I'm not 100% sure) for 85 bit. Do tests with 1000 keys each.

I got the idea, more tests , less variance. If anyone interested, here is my tames generation script which works with your kangaroo_wild. Maybe a lot of things to do and make it better. https://github.com/providiu/tames-gen/ It might be not fully functional but to get an ideea about tames generations. Also requires a modified version of kangaroo_wild.c Hunting for puzzles with CPU is a dead end anyway.

I never said that this program is about finding 135 key, it is about 74-80 bit range search on normal pc without gpu. If you can access to a pc with 192 cores / 192 thread you can use it to search 85-90 bit, but the db is build and optimized for the 74-75 range.

To generate a DB 77 it take about 12 days and also a lot of RAM and SSD space needed.

From 74-75  to 76-77 you need to recover 2 bits:  or you pass from 2GB+4GB to 2GB+16GB, or you pass to 2GB + 8GB and from 16 global bits to 17 global bits and in the tame phase you can exploit all the power of your pc:  384 x 256 --> 2.2 G steps/s

I will try to generate a DB 77 but it will take a lot of time. I will let you know when finishes and made some tests.

Or you can just store DPs continuously as they are found, with zero RAM overhead, and simply improve the DB each and every time a new DLP is solved. If you need a lot of RAM and 12 days, you have a bad understanding / bad implementation of the algorithm... if the purpose is to build a static DB of "best DPs", this is only "best" for the solver parameters (computing power) that you have in mind, and would not help at all solving higher ranges, or solving via something magnitudes of times faster (such as a GPU large-scale cluster).