Introduction
Collatz numbers follow the sequence until x(n) is 1....
odd numbers are multiplied by 3 and increased by 1
even numbers are divided by 2
or (with shifting)
x(n) = initial
if x(n) even then x(n + 1) = x(n) >> 1 else x(n + 1) = x(n) << 1 + x(n) + 1
Quickstart
Performance#FullKubernetesClusterCPUSaturation
Artifacts
| Repo | ||
| jenkins | ||
| sonar | ||
| dev | ||
| prod | ||
| Jiras | https://github.com/obrienlabs/collatz/issues/1 COLLATZ-1 - Getting issue details... STATUS |
Requirements
Including assumptions
| R# | A# | Details | |
|---|---|---|---|
| R1 | Optimize computation using parallel processing | ||
| R2 | Optimize computation by maintaining a map of previous sequences | ||
Analysis
Map/Graph lookup for sequence truncation
The goal of computing the collatz sequence for a particular number is to iterate the sequence to 1. Since we have previously computed sequences that we will eventually revisit when running higher numbers - we must optimize collatz sequence generation by storing previous sequences for query. For example, the trivial sequence 8,4,2,1 is a subset of 32,16,8,4,2,1
API
Architecture
Use Cases
Design
Including implementation
4 Comments
Michael O'Brien
ARM 64
benchmark
macmini110 docker % ./build.sh
[+] Building 85.6s (10/10) FINISHED
=> [internal] load build definition from DockerFile_arm 0.1s
=> => transferring dockerfile: 437B 0.0s
=> [internal] load .dockerignore 0.1s
=> => transferring context: 2B 0.0s
=> [internal] load metadata for docker.io/arm64v8/openjdk:latest 1.3s
=> [auth] arm64v8/openjdk:pull token for registry-1.docker.io 0.0s
=> [1/4] FROM docker.io/arm64v8/openjdk@sha256:3e039585e4bd408d8e0543644e6231c436f9064f928b6ea4347313af1c865bb2 82.9s
=> => resolve docker.io/arm64v8/openjdk@sha256:3e039585e4bd408d8e0543644e6231c436f9064f928b6ea4347313af1c865bb2 0.0s
=> => sha256:3e039585e4bd408d8e0543644e6231c436f9064f928b6ea4347313af1c865bb2 462B / 462B 0.0s
=> => sha256:41b5e4d2891710bab81d2a4534dbe3524e3d45528d9815a8a893475583b1cbee 954B / 954B 0.0s
=> => sha256:252c9182247fa77a952ce0d76c9f0a9068649bcc2a196b8e8352e780043c5ef3 4.44kB / 4.44kB 0.0s
=> => sha256:a1eec3e47437e3334dd709f3a36be617982ec7579fa52be305301bb95c0d4be1 41.88MB / 41.88MB 2.0s
=> => sha256:11ec5552a84ea6485845e8e0a4d9b09b5e8f78d742440c18650d1ec9b1aacd89 14.27MB / 14.27MB 1.3s
=> => sha256:f9f8be97c8dc92aacf1496f9d52945fd57b624dba98e8062e19d6de766d6d712 185.95MB / 185.95MB 76.0s
=> => extracting sha256:a1eec3e47437e3334dd709f3a36be617982ec7579fa52be305301bb95c0d4be1 3.3s
=> => extracting sha256:11ec5552a84ea6485845e8e0a4d9b09b5e8f78d742440c18650d1ec9b1aacd89 1.0s
=> => extracting sha256:f9f8be97c8dc92aacf1496f9d52945fd57b624dba98e8062e19d6de766d6d712 6.6s
=> [internal] load build context 0.0s
=> => transferring context: 10.32kB 0.0s
=> [2/4] RUN mkdir -p /opt/app/ 0.9s
=> [3/4] ADD org.obrienscience.collatz.server.ForkJoinCollatzServer*.jar /opt/app//lib/org.obrienscience.collatz.server.ForkJoinCollatzServer.jar 0.0s
=> [4/4] ADD startService.sh /opt/app//bin/ 0.1s
=> exporting to image 0.1s
=> => exporting layers 0.1s
=> => writing image sha256:e105c37adacac91299dd97e765568646d4dd5481a333c8e487cf4c9ab9917634 0.0s
=> => naming to docker.io/obrienlabs/collatz-se 0.0s
Use 'docker scan' to run Snyk tests against images to find vulnerabilities and learn how to fix them
The push refers to repository [docker.io/obrienlabs/collatz-se]
a79977b46fd5: Pushed
c37cc5d48679: Pushed
b6fb6f506035: Pushed
79e24aec32e5: Mounted from arm64v8/openjdk
afacf90f401e: Mounted from arm64v8/openjdk
f6c0bde932b6: Mounted from arm64v8/openjdk
arm: digest: sha256:1e5c975e86bcb603427c854ca1bc59ae84056b1ec96469fda512287dddac6726 size: 1576
Michael O'Brien
lenovo P17 xeon W-10855M 2.8g 4.5G single thread
S: 17316457353 M: 20722398914405051728 P: 559 T: 319001
S: 17387835787 M: 319497287463520 P: 1138 T: 161643
S: 17828259369 M: 319497287463520 P: 1213 T: 971959
S: 23035537407 M: 68838156641548227040 P: 836 T: 11760767
S: 31694683323 M: 319497287463520 P: 1219 T: 19872258
Total time: 39285195
32.33 above
37 38 now
124,21267647932558653966460912964485513216
125,42535295865117307932921825928971026432
126,85070591730234615865843651857942052864
127,170141183460469231731687303715884105728
128,340282366920938463463374607431768211456
p: 1132 v: 18144594937356598024
S: 137489184151 M: 1037298361093936 P: 1203 T: 130286
S: 137615886815 M: 82341648902022834004 P: 554 T: 332674
S: 137971563859 M: 114639617141613998440 P: 774 T: 892844
S: 138851549183 M: 311852866932316368484 P: 717 T: 2188141
S: 140282519551 M: 420967113788389829704 P: 1110 T: 3583725
S: 142626074957 M: 319497287463520 P: 1216 T: 5836036
S: 146990792361 M: 1372453649566268380360 P: 575 T: 10889422
S: 150256276495 M: 319497287463520 P: 1229 T: 8141611
S: 158294678119 M: 319497287463520 P: 1242 T: 20128815
S: 166763117679 M: 319497287463520 P: 1255 T: 21198735
S: 202485402111 M: 2662567439048656 P: 1307 T: 90195201
S: 204430613247 M: 1415260793009654991088 P: 790 T: 4961915
S: 231913730799 M: 2190343823882874513556 P: 586 T: 69982310
MBP 2021 - 3.4G M1Max 32g
38 39
p: 1219 v: 68838156641548227040
S: 275231773629 M: 82341648902022834004 P: 555 T: 1655883
S: 275567248831 M: 135401069459613440176 P: 607 T: 1125241
S: 275791511321 M: 916613029076867799856 P: 762 T: 694994
S: 275969838571 M: 1190241831184086616360 P: 612 T: 571765
S: 277625049031 M: 319497287463520 P: 1279 T: 5652315
S: 293981584723 M: 1372453649566268380360 P: 576 T: 45481865
current max (40-41)
1356
(39-40)
24
100540173225585986235988
mbp
40-41
p: 1307 v: 2190343823882874513556
S: 1101223847935 M: 5629053962119999674580 P: 689 T: 9757118
S: 1110940858087 M: 13128150288877122866848 P: 800 T: 65850832
S: 1115138883691 M: 39533276910778060381072 P: 808 T: 33128984
S: 1122382791663 M: 2662567439048656 P: 1356 T: 54274522
39-40
S: 559328194559 M: 5354731275039554391376 P: 670 T: 78805194
S: 566696709991 M: 12067738864544340542752 P: 882 T: 43213432
S: 567839862631 M: 100540173225585986235988 P: 789 T: 6270127
S: 568847878633 M: 2662567439048656 P: 1324 T: 8069123
39-39
S: 275231773629 M: 82341648902022834004 P: 555 T: 1655883
S: 275567248831 M: 135401069459613440176 P: 607 T: 1125241
S: 275791511321 M: 916613029076867799856 P: 762 T: 694994
S: 275969838571 M: 1190241831184086616360 P: 612 T: 571765
S: 277625049031 M: 319497287463520 P: 1279 T: 5652315
S: 293981584723 M: 1372453649566268380360 P: 576 T: 45481865
S: 303728103167 M: 2662567439048656 P: 1305 T: 30891977
S: 306645919871 M: 1415260793009654991088 P: 788 T: 13458574
S: 317311428075 M: 1600148831692109582464 P: 770 T: 49741532
S: 331453744923 M: 5354731275039554391376 P: 677 T: 78809548
Michael O'Brien
https://developer.apple.com/documentation/metal/performing_calculations_on_a_gpu
Michael O'Brien
lenovo P17 top
37 38
S: 231913730799 M: 2190343823882874513556 P: 586 T: 69982310
p: 1132 v: 18144594937356598024
S: 137489184151 M: 1037298361093936 P: 1203 T: 130286
S: 137615886815 M: 82341648902022834004 P: 554 T: 332674
S: 137971563859 M: 114639617141613998440 P: 774 T: 892844
S: 138851549183 M: 311852866932316368484 P: 717 T: 2188141
S: 140282519551 M: 420967113788389829704 P: 1110 T: 3583725
S: 142626074957 M: 319497287463520 P: 1216 T: 5836036
S: 146990792361 M: 1372453649566268380360 P: 575 T: 10889422
S: 150256276495 M: 319497287463520 P: 1229 T: 8141611
S: 158294678119 M: 319497287463520 P: 1242 T: 20128815
S: 166763117679 M: 319497287463520 P: 1255 T: 21198735
S: 202485402111 M: 2662567439048656 P: 1307 T: 90195201
S: 204430613247 M: 1415260793009654991088 P: 790 T: 4961915
S: 231913730799 M: 2190343823882874513556 P: 586 T: 69982310
S: 272025660543 M: 21948483635670417963748 P: 638 T: 102809062
Total time: 348605886
micha@LAPTOP-M4VQDR8K MINGW64 /c/wse_github/benchmark/org.obrienscience.concurrent.CollatzBeowulfSE (master)
$ java -cp target/classes/ org.obrienscience.collatz.model.Collatz 45 46 false
p: 1 v: 1
S: 35184372088833 M: 105553116266500 P: 495 T: 1
S: 35184372088835 M: 158329674399760 P: 327 T: 0
S: 35184372088839 M: 237494511599668 P: 327 T: 1
S: 35184372088847 M: 356241767399584 P: 402 T: 0
S: 35184372088859 M: 25015772549520628 P: 601 T: 0
S: 35184372088915 M: 40070430590253316 P: 539 T: 2
S: 35184372090239 M: 90158468831456596 P: 601 T: 17
S: 35184372092571 M: 107077841008368136 P: 601 T: 20
S: 35184372092663 M: 11712917738216968 P: 676 T: 1
S: 35184372093939 M: 8784688303981960 P: 769 T: 12
S: 35184372095215 M: 168856464739769620 P: 327 T: 12
S: 35184372107983 M: 1081901626523203444 P: 588 T: 62
S: 35184372109727 M: 8122052536739033812 P: 601 T: 11
S: 35184372181545 M: 18737503502092634212 P: 601 T: 477
S: 35184372193699 M: 1650572078674696 P: 813 T: 62
S: 35184372315627 M: 4874877951507268 P: 844 T: 492
S: 35184372981295 M: 31619537878508798164 P: 614 T: 2456
S: 35184373209769 M: 162257842307489534728 P: 707 T: 797
S: 35184373951829 M: 26108157500580976 P: 893 T: 2690
S: 35184381129199 M: 205357627893066262720 P: 650 T: 25490
S: 35184384537465 M: 214603410553167940 P: 1012 T: 11249
S: 35184386532911 M: 216343871665454445064 P: 601 T: 6247
S: 35184386565257 M: 16534643522406669448 P: 1043 T: 100
S: 35184390754217 M: 234668870902506894568 P: 782 T: 13403
S: 35184390806247 M: 375110058493137923764 P: 751 T: 197
S: 35184401537503 M: 821430988033792212880 P: 707 T: 37092
S: 35184411523835 M: 3204555394451485954840 P: 707 T: 34002
S: 35184442553447 M: 39029951209477627312 P: 1255 T: 110921
S: 35184451396679 M: 7493752515693740702632 P: 562 T: 29253
S: 35184478001895 M: 33268027314848835751252 P: 950 T: 90617
S: 35184878951065 M: 79560172378957480 P: 1268 T: 1331705
S: 35184979525727 M: 66537003042720695494816 P: 676 T: 345238
S: 35185162771287 M: 914060150814004 P: 1379 T: 603029
S: 35188558175003 M: 778798735191206232795664 P: 857 T: 11562073
S: 35190771445375 M: 1137034215704975122913056 P: 751 T: 7367520
S: 35195588022095 M: 2410426507079572 P: 1392 T: 16498490
S: 35209881771775 M: 2106406582717832969996896 P: 813 T: 48313908
S: 35238020628851 M: 207936463344549949044875464 P: 813 T: 99325495
S: 35244936739431 M: 107262159535053880 P: 1467 T: 24050211
S: 35327900232039 M: 5459542915117655680 P: 1498 T: 285508449
S: 35358918609903 M: 3023601480870784 P: 1529 T: 105989735
S: 35494485985651 M: 79988992024030705960 P: 1560 T: 467422412
p: 1132 v: 18144594937356598024
S: 137489184151 M: 1037298361093936 P: 1203 T: 130286
S: 137615886815 M: 82341648902022834004 P: 554 T: 332674
S: 137971563859 M: 114639617141613998440 P: 774 T: 892844
S: 138851549183 M: 311852866932316368484 P: 717 T: 2188141
S: 140282519551 M: 420967113788389829704 P: 1110 T: 3583725
S: 142626074957 M: 319497287463520 P: 1216 T: 5836036
S: 146990792361 M: 1372453649566268380360 P: 575 T: 10889422
S: 150256276495 M: 319497287463520 P: 1229 T: 8141611
S: 158294678119 M: 319497287463520 P: 1242 T: 20128815
S: 166763117679 M: 319497287463520 P: 1255 T: 21198735
S: 202485402111 M: 2662567439048656 P: 1307 T: 90195201
S: 204430613247 M: 1415260793009654991088 P: 790 T: 4961915
S: 231913730799 M: 2190343823882874513556 P: 586 T: 69982310
S: 272025660543 M: 21948483635670417963748 P: 638 T: 102809062
Total time: 348605886
micha@LAPTOP-M4VQDR8K MINGW64 /c/wse_github/benchmark/org.obrienscience.concurrent.CollatzBeowulfSE (master)
$ java -cp target/classes/ org.obrienscience.collatz.model.Collatz 37 38 false 1132 18144594937356598024
128,340282366920938463463374607431768211456
p: 1132 v: 18144594937356598024
S: 2199037477753 M: 3041840329528319475892 P: 778 T: 39985
S: 2199194284671 M: 117495840060430216 P: 1176 T: 447137
S: 2199826946417 M: 1037298361093936 P: 1207 T: 1832256
S: 2200105791487 M: 3896105123588134772968 P: 672 T: 796083
S: 2200481279085 M: 32551956638053576 P: 1269 T: 1102451
S: 2200626411745 M: 25309795916763734866720 P: 716 T: 416122
S: 2203368984489 M: 804806784572308 P: 1300 T: 8293363
S: 2206424378249 M: 400558740821250122033728 P: 641 T: 8902814
S: 2226026870207 M: 1219624271099764 P: 1344 T: 58551231
S: 2244765583327 M: 2662567439048656 P: 1357 T: 58467427
S: 2345780341887 M: 101320596844476712 P: 1370 T: 314239447
S: 2366794773743 M: 466908852728752 P: 1401 T: 65827937
S: 2500922855259 M: 79988992024030705960 P: 1414 T: 419070994