Division is the most time-consuming, resource expensive, and complex arithmetic operation. Hardware and software support for floating-point arithmetic is a must in modern central processor units. Even though division is used the least compared to addition and multiplication, it is becoming increasingly important in modern complex applications. The performance of such applications is affected and limited by the algorithms used for division. This project and Report study some of the most used division algorithms such as long division, restoring, non-restoring, SRT, Newton-Raphson, Goldschmidt, accurate quotient approximations, polynomial long division, and polynomial extended synthetic division. The Report continues by comparing the fastest division algorithm with Python’s built-in integer division, divmod function, and polydiv function. Finally, the Report concludes that the Newton-Raphson division algorithm is the fastest for integers, and the polynomial extended synthetic division algorithm is the fastest for polynomials. Moreover, the Report illustrates that Newton-Raphson division algorithm and polynomial extended synthetic division algorithm are faster and more efficient than Python’s built-in algorithms.
Explore the docs »
Report Bug
·
Request Feature
Table of Contents
Division Alogirthms can be categorized into:
1. Division of unsigned integers
2. Division of polynomials
- Excessively test each Division Algorithm with the number of digits starting from 0 and going up to 2,097,153.
- Excessively test each Polynomial Division Algorithm with the degree of the polynomial starting from 5,000 and going up to 300,002.
- A new unique way of implementing Newton Raphson Division Algorithm.
To get a local copy of the Revolutionizing the Division Operation project up and running locally follow these simple example steps:
NOTE: How to check if Python is installed and what is its version
python --versionNOTE: How to check if Git is installed and what is its version
git -v-
Please make sure you have pyenv installed and use Python3 version 3.11.0:
- You can use pyenv to switch between different Python versions:
-
Please make sure you have git installed
-
Please look at the setup folder found in this project to find the directions specific to your operating system. The general instructions can also be found below.
-
Navigate to the directory where you want to clone/run/save the application:
cd your_selected_directory -
Clone this repository:
git clone https://github.com/GeorgiosIoannouCoder/division-algorithms.git
-
Navigate to the realesrgan git repository:
cd division-algorithms -
Use Python3 3.11.0 version in the cloned repository folder:
pyenv local 3.11.0 -
Create virtual environment in the cloned repository folder:
python -m venv .division-algorithms-venv
-
Activate the virtual environment (Windows OR Mac/Linux):
- Windows
.\.division-algorithms-venv\Scripts\activate
- Mac/Linux
source .division-algorithms-venv/bin/activate -
Install the dependencies listed in the requirements.txt file:
pip install -r requirements.txt
-
Install ipykernel:
pip install ipykernel
-
Install Jupyter Notebook:
pip install jupyter notebook
-
Add the kernel of the virtual environment in the Jupyter Notebook:
ipython kernel install --user --name=.division-algorithms-venv
-
Run the Jupyter Notebook:
jupyter notebook
-
Select the .division-algorithms-venv kernel to run the Jupyter Notebook.
-
To Run The Notebook (4 Options):
- Steps above and also here
- Use Google Colaboratory
- Use Jupyter Notebboks Extension for VS Code
- Use Anaconda
- Download and install Anaconda
- Launch a jupyter notebook:
- MacOS users, open up terminal and type in
jupyter notebook - Window users, open up your Anaconda Power Shell, and type in
jupyter notebook
- MacOS users, open up terminal and type in
The full project code with the output can be found here.
The report of this project with a comprehensive explanation of all the Division Algorithms is located here. The figures found inside the Report are located here and here.
The slides of this project are located here.
- Number of atoms in the universe = 1078 to 1082
- Newton Raphson division algorithm = 2,097,153 digits (able to carry the most complex tasks)
- Polynomial extended synthetic division algorithm = 300,002 nd degree polynomials
- Newton Raphson division algorithm is the fastest and faster than Python’s built in functions
- None of the division algorithms is considered as the best
- There is a trade off in choosing what division algorithm to use and it depends on the task needed to be done
From this Report and based on Table A5 and Graph A5, we concluded that the fastest division algorithm for large-scale complex tasks is the Newton Raphson division algorithm. However, it is also expected that the Goldschmidt division algorithm and the accurate quotient approximations division algorithm will also be fast. The Newton Raphson division algorithm is so fast that the Python programming language may want to override its integer division algorithm with this algorithm. For smaller scale and simpler tasks, the long division algorithm can also be used.
For polynomial division it is better to implement the polynomial extended synthetic division algorithm rather than the polynomial long division algorithm because it is faster, simpler, and uses fewer resources. The Python programming language may also consider in overriding its polydiv function with the polynomial extended synthetic division algorithm because it solves the issue of memory.
Below are the Figures found inside the Appendix and Slides.
- WE CAN CLEARLY SEE FROM THE FIGURES BELOW THAT THIS PROJECT'S IMPLEMENTATION OF NEWTON RAPHSON DIVISION ALGORITHM WITH 81.322562 seconds BEATS PYTHON'S divmod FUNCTION WITH 82.013895 seconds AND PYTHON'S INTEGER DIVISION WITH 84.886254 seconds.
Contributions are what make the open source community such an amazing place to learn, inspire, and create. Any contributions you make are greatly appreciated.
If you have a suggestion that would make this better, please fork the repo and create a pull request. You can also simply open an issue with the tag "enhancement". Don't forget to give the project a star! Thanks again!
- Fork the Project
- Create your Feature Branch (
git checkout -b feature/AmazingFeature) - Commit your Changes (
git commit -m 'Add some AmazingFeature') - Push to the Branch (
git push origin feature/AmazingFeature) - Open a Pull Request
Distributed under the MIT License. See LICENSE for more information.
MIT License
Copyright (c) 2021 Georgios Ioannou
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Georgios Ioannou - @LinkedIn
Georgios Ioannou - @georgiosioannoucoder - Please contact me via the form in my portfolio.
Project Link: https://github.com/GeorgiosIoannouCoder/division-algorithms