Pure Python implementation of DJB's Batch GCD algorithm
Project description
Batch GCD
Overview
A pure Python implementation of DJB's Batch GCD algorithm.
Installation
Download and install with pip
.
Or, download from source and install with make install
(standard, user) or make install_dev
(editable, system).
Usage
This is a library and cannot be invoked directly.
Test with make test
.
The batch_gcd
module exposes a batch_gcd
function which takes integers and returns a list of their GCDs at the corresponding index.
>>> # Example batch_gcd usage
>>> from batch_gcd import batch_gcd
>>> batch_gcd(1909, 2923, 291, 205, 989, 62, 451, 1943, 1079, 2419)
[1909, 1, 1, 41, 23, 1, 41, 1, 83, 41]
This calculation involves two intermediate steps: creating a product tree and creating a remainder tree.
These functions are also exposed, as products
and remainders
.
products
take integers and returns a product tree, remainders
takes an integer and a product tree and returns a list of remainders.
Resources
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for batch_gcd-0.0.3-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5401886dc107138dac7a6406158eb3930ac6528b10d51dc7653e8cfdff1cbae0 |
|
MD5 | 2ecced54f252ef1916c509e8c8f5d150 |
|
BLAKE2b-256 | 1fc64718613f39f8a84c636c0e94257f5a7e0135ae9d77415d2b70cb46d46c13 |