yathvi / numbers

Most efficient algorithms in the history

Impressed with ChatGPT for sharing efficient code, few examples below:

ChatGPT output:

Java BigInteger Constructor https://chat.openai.com/share/c2dacb83-395c-4288-90c9-0e4507a84a27

https://github.com/yathvi/BigInteger/blob/main/src/AllCombinationsBigInteger.java

Change List to int[] https://chat.openai.com/share/0d8b8148-09d2-4f90-a2ea-64a016881e1d

Optimizing Java Code https://chat.openai.com/share/16f68fc9-5f56-4860-8d1f-fe071b18d9ed

https://github.com/yathvi/Numbers/blob/main/src/PrimeFactors.java

Most efficient algorithms in the history https://chat.openai.com/share/6e1d661a-ce36-4ffe-b31d-bd3848251fbd

A BigInteger is a data structure in Java that is used to represent very large numerical values = 2147483647 digits. Internally it stores very large numerical values in int array "final int[] mag;"
and perform mathematical/other operations like add, subtract, divide, multiply, pow, gcd, divideAndRemainder, mod, modInverse, modPow and more.......
on this int array to produce final output. you can find find few efficient algorithms in BigInteger class "public class BigInteger extends Number implements Comparable"
and the phrase "This value is found experimentally to work well".

Modified AllCombinationsBigInteger.java code generated by ChatGPT to support m*n positive number combinations.

Recursive.java = RecursiveList.java = NonRecursive.java = NonRecursiveList.java

https://github.com/yathvi/BigInteger/tree/main/src

What is a BigInteger and how to use it in Java

https://nullbeans.com/what-is-a-biginteger-and-how-to-use-it-in-java/

BigInteger Internally stores numerical values in int array "final int[] mag;"

BigInteger value = 1 <===> int[] mag = [1]
BigInteger value = 2 <===> int[] mag = [2]
.
.
BigInteger value = 2147483647 <===> int[] mag = [2147483647]
BigInteger value = 2147483648 <===> int[] mag = [-2147483648] <===> 2 pow 31
BigInteger value = 2147483649 <===> int[] mag = [-2147483647]
.
.
BigInteger value = 4294967294 <===> int[] mag = [-2]
BigInteger value = 4294967295 <===> int[] mag = [-1]
BigInteger value = 4294967296 <===> int[] mag = [1, 0] <===> 2 pow 32
.
.
BigInteger value = 6442450943 <===> int[] mag = [1, 2147483647]
BigInteger value = 6442450944 <===> int[] mag = [1, -2147483648]
.
.
BigInteger value = 8589934591 <===> int[] mag = [1, -1]
BigInteger value = 8589934592 <===> int[] mag = [2, 0] <===> 2 pow 33
.
.
BigInteger value = 1099511627776 <===> int[] mag = [256, 0] <===> 2 pow 40
.
.
BigInteger value = 9223372036854775807 <===> int[] mag = [2147483647, -1]
BigInteger value = 9223372036854775808 <===> int[] mag = [-2147483648, 0] <===> 2 pow 63
.
.
BigInteger value = 9223372039002259455 <===> int[] mag = [-2147483648, 2147483647]
BigInteger value = 9223372039002259456 <===> int[] mag = [-2147483648, -2147483648]
BigInteger value = 9223372039002259457 <===> int[] mag = [-2147483648, -2147483647]
.
.
BigInteger value = 18446744073709551615 <===> int[] mag = [-1, -1]
BigInteger value = 18446744073709551616 <===> int[] mag = [1, 0, 0] <===> 2 pow 64
.
.
BigInteger value = 115792089237316195423570985008687907853269984665640564039457584007913129639935 <===> int[] mag = [-1, -1, -1, -1, -1, -1, -1, -1]
BigInteger value = 115792089237316195423570985008687907853269984665640564039457584007913129639936 <===> int[] mag = [1, 0, 0, 0, 0, 0, 0, 0, 0] <===> 2 pow 256
.
.
.
.
.

Rubik's cube

The original 3x3x3 Rubik's cube has 43 252 003 274 489 856 000 combinations, or 43 quintillion.

Why Are There 43,252,003,274,489,856,000 Rubik's Cube Combinations?

https://www.youtube.com/watch?v=z2-d0x_qxSM

God's Number is 20

Every position of Rubik's Cube can be solved in twenty moves or less.
http://www.cube20.org

For 3x3x3 Rubik's cube
6 face = 6 color
each face = 9 positions

May be we can find different combinations by substituting n = 9 and maxDigit/i = 6 in any of the below code:
Recursive.java = RecursiveList.java = NonRecursive.java = NonRecursiveList.java

https://github.com/yathvi/BigInteger/blob/main/src/Recursive.java
or
https://github.com/yathvi/BigInteger/tree/main/src

0 0 0 0 0 0 0 0 0 <==> count = 1
0 0 0 0 0 0 0 0 1 <==> count = 2
.
.
0 5 5 5 5 5 5 5 4 <==> count = 1679615
0 5 5 5 5 5 5 5 5 <==> count = 1679616
1 0 0 0 0 0 0 0 0 <==> count = 1679617
.
.

Ideally each face will have less than 1679616 combinations, since you cannot have 3 things

1. Twisted Corner (Single Corner Twist)
2. Flipped Edge (Single Edge Flip)
3. Swapped Edges (2 Pieces Swapped)

The algorithmic trick that solves Rubik’s Cubes and breaks ciphers

https://www.youtube.com/watch?v=wL3uWO-KLUE

There is a famous generalization of this phenomenon called six degrees of separation. It says that you can reach almost any person on earth through just six intermediate friends. Researches have verified that on facebook you can reach pretty much anybody through just 4 intermediate friends.

Different sized Rubik's cube, Number Of Combinations

https://www.therubikzone.com/number-of-combinations/

God's algorithm

https://en.wikipedia.org/wiki/God%27s_algorithm
.
.
.
.
.
.
How Quantum Computers Break The Internet... Starting Now

https://www.youtube.com/watch?v=-UrdExQW0cs

A sufficiently large Quantum Computer, if built, would be capable of undermining all widely-deployed Public Key Algorithms used for Key establishment and Digital Signatures.

RSA Algorithm
General Number Field Sieve

https://github.com/yathvi/Numbers/blob/main/src/PrimeFactors.java

Every Number is a Product of Prime Numbers (Prime Factors). For Example between 0 and 100000 there are 9592 prime numbers which can be stored in a Map as below.

1. Prime Numbers Map Size --> 9592 Each of 9592 entries (Prime numbers) in a Map will have corresponding number of occurrences (Count of prime factors between 0 and 100000 which are in the list).
2. Prime Number Count Map Size --> 252 Each of 252 entries (Number of times the Prime Numbers repeated) in a Map will have corresponding Prime Numbers count.

Fact about Numbers that feels like magic. N = p * q
g pow r = mN + 1

The Remainders cycle and they will just keep cycling.
There will always be a remainder of 1. because any number raised to power of 0 = 1

https://github.com/yathvi/Numbers/blob/main/src/RemainderOfOne.java

NIST announces First Four Quantum-Resistant Cryptographic Algorithms
3 of them are based on the mathematics of latices.
.
.
.
.
.
.
How are Images Compressed? [46MB ↘↘ 4.07MB] JPEG In Depth

https://www.youtube.com/watch?v=Kv1Hiv3ox8I

To begin lets take a quick 26 seconds to understand the importance of this algorithm.

1. Smartphones and cameras use JPEG.
2. The majority of images on the internet are in the .jpeg format.
3. Video compression algorithms like h.264, which is a common upload format on YouTube, share techniques found in JPEG compression.
4. Compression algorithms such as JPEG save servers Zettabytes of storage. Resulting in cost reduction.
5. Our world is run by algorithms: search, recommendation, warehouse/shipping logistics, banking, crypto, maps and many more.
6. JPEG is simple compared to these algorithms and worth learning.

JPEG Compression Algorithm

1. Color Space Conversion
2. Chrominance Downsampling
3. Discrete Cosine Transform
4. Quantization
5. Run Length and Huffman Encoding

Human eye have their nuances and jpeg exploits these nuances to remove information that our eyes are not great at perceiving.

For example in human eye there are 2 types of light receptive cells
Rods and Cones
Rods are not color sensitive
Cones have color receptors of Red Green and Blue

Luminance
Chrominance

Every pixel has Red Blue Green combination

Red (R) + Green (G) + Blue (B) ==> Luminance (Y) + Red Chrominance (Cb) + Blue Chrominance(Cr)

.
.
.

H.246 also called AVC (Advanced Video Coding) is currently compression algorithm for uploading videos to YouTube.
And it uses techniques such as chrominance down sampling or chroma subsampling, as well as variations of Discrete Cosine Transform and Quantization.

H.246 ==> Instead of compressing a single static image as in jpeg Video compression must compress 24 to 60 or more frames for every second of video.
It uses intra frames or iframes which is similar to jpeg images for one out of every 30 frames, and then for other 29 frames it uses prediction or bi-directional prediction to only code for the difference and motion while using previously decoded frames as reference.
Note that the frequency of iframes varies widely and there is typically an iframe at the start of every scene change as prediction doesn't work well across scene changes.
.
.
.
Its truly amazing how your smartphone can take images composed of millions of pixels and then perform calculations on every eight by eight block of pixels compressing all that data in to just a couple dozen numbers and then turning around and uncompressing the image faster than it takes you to swipe your finger across the screen.

for example
4032 * 3024 = 12192768 pixels

12192768/64 = 190512 blocks of luminance
190512/4 = 47628 * 2 blocks of chrominance
.
.
.
.
.
.

Some other links:

Rubik's Cube: Why are some cases impossible to solve?

https://www.youtube.com/watch?v=o-RxLzRe2YE

The Simplest Math Problem No One Can Solve - Collatz Conjecture

https://www.youtube.com/watch?v=094y1Z2wpJg

Every positive integer, if you apply these rules, will eventually end up in the four, two, one loop.

Collatz Conjecture
Ulam Conjecture
Kakutani's Problem
Thwaites Conjecture
Hasse's Algorithm
Syracuse Problem
3N+1