Fast recursive division

Burnikel, Christoph; Ziegler, Joachim

Local TagsRelease HistoryDetailsSummary

Fast recursive division

Burnikel, C., & Ziegler, J.(1998). Fast recursive division (MPI-I-1998-1-022). Saarbrücken: Max-Planck-Institut für Informatik.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-7B75-8 Version Permalink: https://hdl.handle.net/21.11116/0000-0001-7534-1

Genre: Report

Files

show Files

hide Files

:

MPI-I-98-1-022.pdf (Any fulltext), 429KB

View Save

File Permalink:
https://hdl.handle.net/21.11116/0000-0001-7535-0

Name:
MPI-I-98-1-022.pdf

Description:
-

OA-Status:

Visibility:
Public

MIME-Type / Checksum:
application/pdf / [MD5]

Technical Metadata:

View

Copyright Date:
-

Copyright Info:
-

License:
-

Locators

show

Creators

show

hide

Creators:
Burnikel, Christoph¹, Author
Ziegler, Joachim¹, Author

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

Content

show

hide

Free keywords: -

Abstract: We present a new recursive method for division with remainder of integers. Its running time is $2K(n)+O(n \log n)$ for division of a $2n$-digit number by an $n$-digit number where $K(n)$ is the Karatsuba multiplication time. It pays in p ractice for numbers with 860 bits or more. Then we show how we can lower this bo und to $3/2 K(n)+O(n\log n)$ if we are not interested in the remainder. As an application of division with remainder we show how to speedup modular multiplication. We also give practical results of an implementation that allow u s to say that we have the fastest integer division on a SPARC architecture compa red to all other integer packages we know of.

Details

show

hide

Language(s): eng - English

Dates: Date issued: 1998

Publication Status: Issued

Pages: 29 p.

Publishing info: Saarbrücken : Max-Planck-Institut für Informatik

Table of Contents: -

Rev. Type: -

Identifiers: Report Nr.: MPI-I-1998-1-022
BibTex Citekey: BurnikelZiegler98

Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show

hide

Title: Research Report / Max-Planck-Institut für Informatik

Source Genre: Series

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -