Notes: A 3SUM algorithm on the binary addition level of atomic generated real numbers

Notes, id: notes_000X

Abstract

We present a simple algorithm for the 3SUM problem for a list L of n real numbers. For this, we generate real numbers with the help of a set I_{a} of so called 'Atomic irrational numbers'. We can show that our algorithm, which use the binary representation of integers, takes time complexity O(nb + U^{1.58}) for an universe of U := 2^{b} distinguishable rational numbers and with our so generated real numbers it takes a time complexity of O(nb|I_{a}| + U^{1.58}_{I_{a}}) on an universe of U_{I_{a}} := 2^{b |I_{a}|} distinguishable real numbers.

Discussions

In the sub directory 'discussion-docs' you can find discussion documents regarding specific points in the notes.

License

See License file.