Skip to content
/ opf Public

Ordered Pairing Functions for Python 3.7+ with support for arbitrarily large integers.

License

Notifications You must be signed in to change notification settings

cerealkill/opf

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

OPF - Ordered Pairing Functions

for Python 3.7+ with support for arbitrarily large integers

Sub-second algorithm for pairing and unpairing non-negative integers. Tests execute under one second with integers up to 7MB large in my laptop. Numbers larger than that take more, even minutes.

Please contribute with more pairing and benchmarks, maybe we find an underlying bottleneck we could fix! :)

Usage

Example with numbers much larger than C ULONG_MAX for 64bit that is 18446744073709551615.

import time
import cantor
import elegant

if __name__ == '__main__':
    # cantor
    start = time.time()
    assert (87917298379182739871892379817239871982379817239871928371923791827398172397129387192379182379182379182739182739187239817329871923791827981723,
            981729837981273971298379812739817239871923791827398172398712983767468675465746172649162486347649289817239) == \
           cantor.unpair(cantor.pair(87917298379182739871892379817239871982379817239871928371923791827398172397129387192379182379182379182739182739187239817329871923791827981723,
                                     981729837981273971298379812739817239871923791827398172398712983767468675465746172649162486347649289817239))
    end = time.time()
    print('cantor\t', '{0:.10f} secs'.format(end - start))
    # elegant
    start = time.time()
    assert (87917298379182739871892379817239871982379817239871928371923791827398172397129387192379182379182379182739182739187239817329871923791827981723,
            981729837981273971298379812739817239871923791827398172398712983767468675465746172649162486347649289817239) == \
           elegant.unpair(elegant.pair(87917298379182739871892379817239871982379817239871928371923791827398172397129387192379182379182379182739182739187239817329871923791827981723,
                                       981729837981273971298379812739817239871923791827398172398712983767468675465746172649162486347649289817239))
    end = time.time()
    print('elegant\t', '{0:.10f} secs'.format(end - start))

# Results:
# cantor	 0.0001599789 secs
# elegant	 0.0000128746 secs

Check test.py for more examples of usage. This package will be made available over pypi once some more pairing algos are added. If you want to publish it, please be kind to let me know before hand. :)

References

To be implemented


PS.: Python 3.8 includes math.isqrt, supposedly slower than the gmpy2 library, dependency for this project. For higher portability just upgrade python and change the libraries to remove this dependency. Kudos to Anders Kaseorg and Mathmandan for pointing this out this fantastic library.

About

Ordered Pairing Functions for Python 3.7+ with support for arbitrarily large integers.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages