kangaroo-wild with precomputed (and chosen) DP

[arulbero]

I wanted to know how fast a normal pc with a normal amount of RAM and without a GPU can retrieve a key in a short range like 2^74 - 2^75.

So I implemented a my 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 about 3s for each key.

It is a bit faster if I search multiple keys in parallel.

The program can retrieve a key in higher range (like 2^77 - 2^78 or  2^80 - 2^81) as well based on the same database.

Size of the database : 6GB.

[dextronomous]

hi there arulbero,

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

[arulbero]

hi there arulbero,

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

Now it should work.

[dextronomous]

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,

[arulbero]

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)

[dextronomous]

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,

[samee2026]

I wanted to know how fast a normal pc with a normal amount of RAM and without a GPU can retrieve a key in a short range like 2^74 - 2^75.

So I implemented a my 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 about 3s for each key.

It is a bit faster if I search multiple keys in parallel.

The program can retrieve a key in higher range (like 2^77 - 2^78 or  2^80 - 2^81) as well based on the same database.

Size of the database : 6GB.

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

@arulbero why deleted git ?

[arulbero]

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,

I wanted to know how fast a normal pc with a normal amount of RAM and without a GPU can retrieve a key in a short range like 2^74 - 2^75.

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:

Code:

 
#define MAX_PARTITIONS 4096   // supports up to 12 extra bits over DB range

if you want to search in the 2**100 - 2**101 range:

Code:

#define MAX_PARTITIONS (1ULL << 26)   // supports up to 26 extra bits over DB 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?

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

@arulbero why deleted git ?

I didn't delete anything, the link is ok.

*********************************************************************************

EDIT: Database updated! Enjoy the speedup!