Division algorithm

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Division algorithm - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"a1b32e01-dc36-4723-9979-c096f0c8ca8e","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Division_algorithm","wgTitle":"Division algorithm","wgCurRevisionId":1246386441,"wgRevisionId":1246386441,"wgArticleId":3336479,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["CS1 maint: location missing publisher","Webarchive template wayback links","Articles with short description","Short description is different from Wikidata","All articles with unsourced statements","Articles with unsourced statements from February 2012","Articles with unsourced statements from February 2014","All pages needing factual verification","Wikipedia articles needing factual verification from June 2015","Articles to be expanded from September 2012", "All articles to be expanded","Articles with example pseudocode","Binary arithmetic","Computer arithmetic","Division (mathematics)","Computer arithmetic algorithms"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Division_algorithm","wgRelevantArticleId":3336479,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgRedirectedFrom":"Goldschmidt_division","wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":40000,"wgInternalRedirectTargetUrl": "/wiki/Division_algorithm#Goldschmidt_division","wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q3526714","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","ext.pygments":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready", "jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["mediawiki.action.view.redirect","ext.cite.ux-enhancements","ext.pygments.view","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Division algorithm - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Division_algorithm#Goldschmidt_division"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Division_algorithm&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Division_algorithm#Goldschmidt_division"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Division_algorithm rootpage-Division_algorithm skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" > Main menu </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z">Main page</a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia">Contents</a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events">Current events</a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x">Random article</a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works">About Wikipedia</a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia">Contact us</a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia">Help</a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia">Learn to edit</a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors">Community portal</a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r">Recent changes</a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia">Upload file</a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"> Search </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" > Appearance </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class="">Donate</a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Division+algorithm" title="You are encouraged to create an account and log in; however, it is not mandatory" class="">Create account</a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Division+algorithm" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class="">Log in</a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" > Personal tools </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en">Donate</a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Division+algorithm" title="You are encouraged to create an account and log in; however, it is not mandatory"> Create account</a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Division+algorithm" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"> Log in</a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing">learn more</a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y">Contributions</a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n">Talk</a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Division_by_repeated_subtraction" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Division_by_repeated_subtraction"> <div class="vector-toc-text"> 1 Division by repeated subtraction </div> </a> <ul id="toc-Division_by_repeated_subtraction-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Long_division" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Long_division"> <div class="vector-toc-text"> 2 Long division </div> </a> <button aria-controls="toc-Long_division-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> Toggle Long division subsection </button> <ul id="toc-Long_division-sublist" class="vector-toc-list"> <li id="toc-Integer_division_(unsigned)_with_remainder" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Integer_division_(unsigned)_with_remainder"> <div class="vector-toc-text"> 2.1 Integer division (unsigned) with remainder </div> </a> <ul id="toc-Integer_division_(unsigned)_with_remainder-sublist" class="vector-toc-list"> <li id="toc-Example" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Example"> <div class="vector-toc-text"> 2.1.1 Example </div> </a> <ul id="toc-Example-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-Slow_division_methods" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Slow_division_methods"> <div class="vector-toc-text"> 3 Slow division methods </div> </a> <button aria-controls="toc-Slow_division_methods-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> Toggle Slow division methods subsection </button> <ul id="toc-Slow_division_methods-sublist" class="vector-toc-list"> <li id="toc-Restoring_division" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Restoring_division"> <div class="vector-toc-text"> 3.1 Restoring division </div> </a> <ul id="toc-Restoring_division-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Non-restoring_division" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Non-restoring_division"> <div class="vector-toc-text"> 3.2 Non-restoring division </div> </a> <ul id="toc-Non-restoring_division-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-SRT_division" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#SRT_division"> <div class="vector-toc-text"> 3.3 SRT division </div> </a> <ul id="toc-SRT_division-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Fast_division_methods" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Fast_division_methods"> <div class="vector-toc-text"> 4 Fast division methods </div> </a> <button aria-controls="toc-Fast_division_methods-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> Toggle Fast division methods subsection </button> <ul id="toc-Fast_division_methods-sublist" class="vector-toc-list"> <li id="toc-Newton–Raphson_division" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Newton–Raphson_division"> <div class="vector-toc-text"> 4.1 Newton–Raphson division </div> </a> <ul id="toc-Newton–Raphson_division-sublist" class="vector-toc-list"> <li id="toc-Pseudocode" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Pseudocode"> <div class="vector-toc-text"> 4.1.1 Pseudocode </div> </a> <ul id="toc-Pseudocode-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Variant_Newton–Raphson_division" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Variant_Newton–Raphson_division"> <div class="vector-toc-text"> 4.1.2 Variant Newton–Raphson division </div> </a> <ul id="toc-Variant_Newton–Raphson_division-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Goldschmidt_division" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Goldschmidt_division"> <div class="vector-toc-text"> 4.2 Goldschmidt division </div> </a> <ul id="toc-Goldschmidt_division-sublist" class="vector-toc-list"> <li id="toc-Binomial_theorem" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Binomial_theorem"> <div class="vector-toc-text"> 4.2.1 Binomial theorem </div> </a> <ul id="toc-Binomial_theorem-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-Large-integer_methods" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Large-integer_methods"> <div class="vector-toc-text"> 5 Large-integer methods </div> </a> <ul id="toc-Large-integer_methods-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Division_by_a_constant" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Division_by_a_constant"> <div class="vector-toc-text"> 6 Division by a constant </div> </a> <ul id="toc-Division_by_a_constant-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Rounding_error" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Rounding_error"> <div class="vector-toc-text"> 7 Rounding error </div> </a> <ul id="toc-Rounding_error-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> 8 See also </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> 9 Notes </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> 10 References </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Further_reading" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Further_reading"> <div class="vector-toc-text"> 11 Further reading </div> </a> <ul id="toc-Further_reading-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" > Toggle the table of contents </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading">Division algorithm</h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 4 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-4" aria-hidden="true" > 4 languages </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AA%D9%82%D8%B3%DB%8C%D9%85" title="الگوریتم تقسیم – Persian" lang="fa" hreflang="fa" data-title="الگوریتم تقسیم" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target">فارسی</a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E9%99%A4%E7%AE%97_(%E3%83%87%E3%82%B8%E3%82%BF%E3%83%AB)" title="除算 (デジタル) – Japanese" lang="ja" hreflang="ja" data-title="除算 (デジタル)" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target">日本語</a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F" title="Алгоритм деления – Russian" lang="ru" hreflang="ru" data-title="Алгоритм деления" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target">Русский</a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E9%99%A4%E6%B3%95%E5%99%A8" title="除法器 – Chinese" lang="zh" hreflang="zh" data-title="除法器" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target">中文</a></li> </ul> <div class="after-portlet after-portlet-lang"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q3526714#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Division_algorithm" title="View the content page [c]" accesskey="c">Article</a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Division_algorithm" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t">Talk</a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" >English </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Division_algorithm">Read</a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Division_algorithm&action=edit" title="Edit this page [e]" accesskey="e">Edit</a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Division_algorithm&action=history" title="Past revisions of this page [h]" accesskey="h">View history</a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" >Tools </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Division_algorithm">Read</a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Division_algorithm&action=edit" title="Edit this page [e]" accesskey="e">Edit</a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Division_algorithm&action=history">View history</a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Division_algorithm" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j">What links here</a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Division_algorithm" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k">Related changes</a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u">Upload file</a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q">Special pages</a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Division_algorithm&oldid=1246386441" title="Permanent link to this revision of this page">Permanent link</a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Division_algorithm&action=info" title="More information about this page">Page information</a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Division_algorithm&id=1246386441&wpFormIdentifier=titleform" title="Information on how to cite this page">Cite this page</a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FDivision_algorithm%23Goldschmidt_division">Get shortened URL</a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FDivision_algorithm%23Goldschmidt_division">Download QR code</a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Division_algorithm&action=show-download-screen" title="Download this page as a PDF file">Download as PDF</a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Division_algorithm&printable=yes" title="Printable version of this page [p]" accesskey="p">Printable version</a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q3526714" title="Structured data on this page hosted by Wikidata [g]" accesskey="g">Wikidata item</a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle">(Redirected from <a href="/w/index.php?title=Goldschmidt_division&redirect=no" class="mw-redirect" title="Goldschmidt division">Goldschmidt division</a>)</div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Method for division with remainder</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">This article is about algorithms for division of integers. For the pencil-and-paper algorithm, see <a href="/wiki/Long_division" title="Long division">Long division</a>. For the division algorithm for polynomials, see <a href="/wiki/Polynomial_long_division" title="Polynomial long division">Polynomial long division</a>.</div> A division algorithm is an <a href="/wiki/Algorithm" title="Algorithm">algorithm</a> which, given two <a href="/wiki/Integer" title="Integer">integers</a> N and D (respectively the numerator and the denominator), computes their <a href="/wiki/Quotient" title="Quotient">quotient</a> and/or <a href="/wiki/Remainder" title="Remainder">remainder</a>, the result of <a href="/wiki/Euclidean_division" title="Euclidean division">Euclidean division</a>. Some are applied by hand, while others are employed by digital circuit designs and software. Division algorithms fall into two main categories: slow division and fast division. Slow division algorithms produce one digit of the final quotient per iteration. Examples of slow division include <a href="#Restoring_division">restoring</a>, non-performing restoring, <a href="#Non-restoring_division">non-restoring</a>, and <a href="#SRT_division">SRT</a> division. Fast division methods start with a close approximation to the final quotient and produce twice as many digits of the final quotient on each iteration.<a href="#cite_note-1">[1]</a> <a href="#Newton–Raphson_division">Newton–Raphson</a> and <a href="#Goldschmidt_division">Goldschmidt</a> algorithms fall into this category. Variants of these algorithms allow using fast <a href="/wiki/Multiplication_algorithm" title="Multiplication algorithm">multiplication algorithms</a>. It results that, for large integers, the <a href="/wiki/Computational_complexity" title="Computational complexity">computer time</a> needed for a division is the same, up to a constant factor, as the time needed for a multiplication, whichever multiplication algorithm is used. Discussion will refer to the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N/D=(Q,R)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>D</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>Q</mi> <mo>,</mo> <mi>R</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N/D=(Q,R)}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7b17784c65376a63bc09d62ba764d95203bea985" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.694ex; height:2.843ex;" alt="{\displaystyle N/D=(Q,R)}">, where <ul><li>N = <a href="/wiki/Fraction" title="Fraction">numerator</a> (dividend)</li> <li>D = <a href="/wiki/Fraction" title="Fraction">denominator</a> (divisor)</li></ul> is the input, and <ul><li>Q = <a href="/wiki/Quotient" title="Quotient">quotient</a></li> <li>R = <a href="/wiki/Remainder" title="Remainder">remainder</a></li></ul> is the output. <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Division_by_repeated_subtraction">Division by repeated subtraction</h2>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=1" title="Edit section: Division by repeated subtraction">edit</a>]</div> The simplest division algorithm, historically incorporated into a <a href="/wiki/Greatest_common_divisor" title="Greatest common divisor">greatest common divisor</a> algorithm presented in <a href="/wiki/Euclid%27s_Elements" title="Euclid's Elements">Euclid's Elements</a>, Book VII, Proposition 1, finds the remainder given two positive integers using only subtractions and comparisons: <div class="mw-highlight mw-highlight-lang-lua mw-content-ltr" dir="ltr"><pre>R := N Q := 0 while R ≥ D do R := R − D Q := Q + 1 end return (Q,R) </pre></div> The proof that the quotient and remainder exist and are unique (described at <a href="/wiki/Euclidean_division" title="Euclidean division">Euclidean division</a>) gives rise to a complete division algorithm, applicable to both negative and positive numbers, using additions, subtractions, and comparisons: <div class="mw-highlight mw-highlight-lang-lua mw-content-ltr" dir="ltr"><pre>function divide(N, D) if D = 0 then error(DivisionByZero) end if D < 0 then (Q, R) := divide(N, −D); return (−Q, R) end if N < 0 then (Q,R) := divide(−N, D) if R = 0 then return (−Q, 0) else return (−Q − 1, D − R) end end -- At this point, N ≥ 0 and D > 0 return divide_unsigned(N, D) end function divide_unsigned(N, D) Q := 0; R := N while R ≥ D do Q := Q + 1 R := R − D end return (Q, R) end </pre></div> This procedure always produces R ≥ 0. Although very simple, it takes Ω(Q) steps, and so is exponentially slower than even slow division algorithms like long division. It is useful if Q is known to be small (being an <a href="/wiki/Output-sensitive_algorithm" title="Output-sensitive algorithm">output-sensitive algorithm</a>), and can serve as an executable specification. <div class="mw-heading mw-heading2"><h2 id="Long_division">Long division</h2>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=2" title="Edit section: Long division">edit</a>]</div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Long_division#Algorithm_for_arbitrary_base" title="Long division">Long division § Algorithm for arbitrary base</a></div> Long division is the standard algorithm used for pen-and-paper division of multi-digit numbers expressed in decimal notation. It shifts gradually from the left to the right end of the dividend, subtracting the largest possible multiple of the divisor (at the digit level) at each stage; the multiples then become the digits of the quotient, and the final difference is then the remainder. When used with a binary radix, this method forms the basis for the (unsigned) integer division with remainder algorithm below. <a href="/wiki/Short_division" title="Short division">Short division</a> is an abbreviated form of long division suitable for one-digit divisors. <a href="/wiki/Chunking_(division)" title="Chunking (division)">Chunking</a> – also known as the partial quotients method or the hangman method – is a less-efficient form of long division which may be easier to understand. By allowing one to subtract more multiples than what one currently has at each stage, a more freeform variant of long division can be developed as well. <div class="mw-heading mw-heading3"><h3 id="Integer_division_(unsigned)_with_remainder">Integer division (unsigned) with remainder</h3>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=3" title="Edit section: Integer division (unsigned) with remainder">edit</a>]</div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">See also: <a href="/wiki/Binary_number#Division" title="Binary number">Binary number § Division</a></div> The following algorithm, the binary version of the famous <a href="/wiki/Long_division" title="Long division">long division</a>, will divide N by D, placing the quotient in Q and the remainder in R. In the following pseudo-code, all values are treated as unsigned integers. <div class="mw-highlight mw-highlight-lang-lua mw-content-ltr" dir="ltr"><pre>if D = 0 then error(DivisionByZeroException) end Q := 0 -- Initialize quotient and remainder to zero R := 0 for i := n − 1 .. 0 do -- Where n is number of bits in N R := R << 1 -- Left-shift R by 1 bit R(0) := N(i) -- Set the least-significant bit of R equal to bit i of the numerator if R ≥ D then R := R − D Q(i) := 1 end end </pre></div> <div class="mw-heading mw-heading4"><h4 id="Example">Example</h4>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=4" title="Edit section: Example">edit</a>]</div> If we take N=11002 (1210) and D=1002 (410) Step 1: Set R=0 and Q=0 Step 2: Take i=3 (one less than the number of bits in N) Step 3: R=00 (left shifted by 1) Step 4: R=01 (setting R(0) to N(i)) Step 5: R < D, so skip statement Step 2: Set i=2 Step 3: R=010 Step 4: R=011 Step 5: R < D, statement skipped Step 2: Set i=1 Step 3: R=0110 Step 4: R=0110 Step 5: R>=D, statement entered Step 5b: R=10 (R−D) Step 5c: Q=10 (setting Q(i) to 1) Step 2: Set i=0 Step 3: R=100 Step 4: R=100 Step 5: R>=D, statement entered Step 5b: R=0 (R−D) Step 5c: Q=11 (setting Q(i) to 1) end Q=112 (310) and R=0. <div class="mw-heading mw-heading2"><h2 id="Slow_division_methods">Slow division methods</h2>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=5" title="Edit section: Slow division methods">edit</a>]</div> Slow division methods are all based on a standard recurrence equation <a href="#cite_note-2">[2]</a> <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{j+1}=B\times R_{j}-q_{n-(j+1)}\times D,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mi>B</mi> <mo>×</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo>−</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mo stretchy="false">(</mo> <mi>j</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msub> <mo>×</mo> <mi>D</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{j+1}=B\times R_{j}-q_{n-(j+1)}\times D,}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2061a50ce24d8a03d89503cff51bca6438d0714c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:30.994ex; height:3.009ex;" alt="{\displaystyle R_{j+1}=B\times R_{j}-q_{n-(j+1)}\times D,}"></dd></dl> where: <ul><li>Rj is the j-th partial remainder of the division</li> <li>B is the <a href="/wiki/Radix" title="Radix">radix</a> (base, usually 2 internally in computers and calculators)</li> <li>q n − (j + 1) is the digit of the quotient in position n−(j+1), where the digit positions are numbered from least-significant 0 to most significant n−1</li> <li>n is number of digits in the quotient</li> <li>D is the divisor</li></ul> <div class="mw-heading mw-heading3"><h3 id="Restoring_division">Restoring division</h3>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=6" title="Edit section: Restoring division">edit</a>]</div> Restoring division operates on <a href="/wiki/Fixed_point_arithmetic" class="mw-redirect" title="Fixed point arithmetic">fixed-point</a> fractional numbers and depends on the assumption 0 < D < N. [<a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed">citation needed</a>] The quotient digits q are formed from the digit set {0,1}. The basic algorithm for binary (radix 2) restoring division is: <div class="mw-highlight mw-highlight-lang-lua mw-content-ltr" dir="ltr"><pre>R := N D := D << n -- R and D need twice the word width of N and Q for i := n − 1 .. 0 do -- For example 31..0 for 32 bits R := 2 * R − D -- Trial subtraction from shifted value (multiplication by 2 is a shift in binary representation) if R >= 0 then q(i) := 1 -- Result-bit 1 else q(i) := 0 -- Result-bit 0 R := R + D -- New partial remainder is (restored) shifted value end end -- Where: N = numerator, D = denominator, n = #bits, R = partial remainder, q(i) = bit #i of quotient </pre></div> Non-performing restoring division is similar to restoring division except that the value of 2R is saved, so D does not need to be added back in for the case of R < 0. <div class="mw-heading mw-heading3"><h3 id="Non-restoring_division">Non-restoring division</h3>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=7" title="Edit section: Non-restoring division">edit</a>]</div> Non-restoring division uses the digit set {−1, 1} for the quotient digits instead of {0, 1}. The algorithm is more complex, but has the advantage when implemented in hardware that there is only one decision and addition/subtraction per quotient bit; there is no restoring step after the subtraction,<a href="#cite_note-3">[3]</a> which potentially cuts down the numbers of operations by up to half and lets it be executed faster.<a href="#cite_note-4">[4]</a> The basic algorithm for binary (radix 2) non-restoring division of non-negative numbers is: <div class="mw-highlight mw-highlight-lang-lua mw-content-ltr" dir="ltr"><pre>R := N D := D << n -- R and D need twice the word width of N and Q for i = n − 1 .. 0 do -- for example 31..0 for 32 bits if R >= 0 then q(i) := +1 R := 2 * R − D else q(i) := −1 R := 2 * R + D end if end -- Note: N=numerator, D=denominator, n=#bits, R=partial remainder, q(i)=bit #i of quotient. </pre></div> Following this algorithm, the quotient is in a non-standard form consisting of digits of −1 and +1. This form needs to be converted to binary to form the final quotient. Example: <table border="0" cellpadding="0"> <tbody><tr> <td colspan="2">Convert the following quotient to the digit set {0,1}: </td></tr> <tr> <td>Start:</td> <td><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> <mo>=</mo> <mn>111</mn> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mn>1</mn> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mn>1</mn> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mn>1</mn> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ff1c6deb0ef9ed263044261ae08c4f75dff7944e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.236ex; height:2.843ex;" alt="{\displaystyle Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}}"> </td></tr> <tr> <td>1. Form the positive term:</td> <td><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=11101010\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo>=</mo> <mn>11101010</mn> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P=11101010\,}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/00a969b72bea5caf34bc5f673174c1aac75ca10b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:14.531ex; height:2.176ex;" alt="{\displaystyle P=11101010\,}"> </td></tr> <tr> <td>2. Mask the negative term*:</td> <td><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M=00010101\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>M</mi> <mo>=</mo> <mn>00010101</mn> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle M=00010101\,}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5e944f1f61ca3ce53751c497b3ddc233d0e24e39" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:15.227ex; height:2.176ex;" alt="{\displaystyle M=00010101\,}"> </td></tr> <tr> <td>3. Subtract: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P-M}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo>−</mo> <mi>M</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P-M}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bc08dd736707753293e96c9cc88f4485bd386d4d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.028ex; height:2.343ex;" alt="{\displaystyle P-M}">:</td> <td><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q=11010101\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> <mo>=</mo> <mn>11010101</mn> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q=11010101\,}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/70cada62fee03b73cd8a2e51dec51fb4c7409c02" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.624ex; height:2.509ex;" alt="{\displaystyle Q=11010101\,}"> </td></tr> <tr> <td colspan="2">*.( Signed binary notation with <a href="/wiki/Ones%27_complement" title="Ones' complement">ones' complement</a> without <a href="/wiki/Two%27s_complement" title="Two's complement">two's complement</a>) </td></tr></tbody></table> If the −1 digits of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}"> are stored as zeros (0) as is common, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}"> and computing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>M</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle M}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}"> is trivial: perform a ones' complement (bit by bit complement) on the original <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}">. <div class="mw-highlight mw-highlight-lang-lua mw-content-ltr" dir="ltr"><pre>Q := Q − bit.bnot(Q) -- Appropriate if −1 digits in Q are represented as zeros as is common. </pre></div> Finally, quotients computed by this algorithm are always odd, and the remainder in R is in the range −D ≤ R < D. For example, 5 / 2 = 3 R −1. To convert to a positive remainder, do a single restoring step after Q is converted from non-standard form to standard form: <div class="mw-highlight mw-highlight-lang-lua mw-content-ltr" dir="ltr"><pre>if R < 0 then Q := Q − 1 R := R + D -- Needed only if the remainder is of interest. end if </pre></div> The actual remainder is R >> n. (As with restoring division, the low-order bits of R are used up at the same rate as bits of the quotient Q are produced, and it is common to use a single shift register for both.) <div class="mw-heading mw-heading3"><h3 id="SRT_division">SRT division</h3>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=8" title="Edit section: SRT division">edit</a>]</div> SRT division is a popular method for division in many <a href="/wiki/Microprocessor" title="Microprocessor">microprocessor</a> implementations.<a href="#cite_note-5">[5]</a><a href="#cite_note-6">[6]</a> The algorithm is named after D. W. Sweeney of <a href="/wiki/IBM" title="IBM">IBM</a>, James E. Robertson of <a href="/wiki/University_of_Illinois" class="mw-redirect" title="University of Illinois">University of Illinois</a>, and <a href="/wiki/K._D._Tocher" title="K. D. Tocher">K. D. Tocher</a> of <a href="/wiki/Imperial_College_London" title="Imperial College London">Imperial College London</a>. They all developed the algorithm independently at approximately the same time (published in February 1957, September 1958, and January 1958 respectively).<a href="#cite_note-7">[7]</a><a href="#cite_note-8">[8]</a><a href="#cite_note-9">[9]</a> SRT division is similar to non-restoring division, but it uses a <a href="/wiki/Lookup_table" title="Lookup table">lookup table</a> based on the dividend and the divisor to determine each quotient digit. The most significant difference is that a redundant representation is used for the quotient. For example, when implementing radix-4 SRT division, each quotient digit is chosen from five possibilities: { −2, −1, 0, +1, +2 }. Because of this, the choice of a quotient digit need not be perfect; later quotient digits can correct for slight errors. (For example, the quotient digit pairs (0, +2) and (1, −2) are equivalent, since 0×4+2 = 1×4−2.) This tolerance allows quotient digits to be selected using only a few most-significant bits of the dividend and divisor, rather than requiring a full-width subtraction. This simplification in turn allows a radix higher than 2 to be used. Like non-restoring division, the final steps are a final full-width subtraction to resolve the last quotient bit, and conversion of the quotient to standard binary form. The <a href="/wiki/Original_Intel_Pentium_(P5_microarchitecture)" class="mw-redirect" title="Original Intel Pentium (P5 microarchitecture)">Intel Pentium</a> processor's <a href="/wiki/Pentium_FDIV_bug" title="Pentium FDIV bug">infamous floating-point division bug</a> was caused by an incorrectly coded lookup table. Five of the 1066 entries had been mistakenly omitted.<a href="#cite_note-10">[10]</a><a href="#cite_note-11">[11]</a> <div class="mw-heading mw-heading2"><h2 id="Fast_division_methods">Fast division methods</h2>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=9" title="Edit section: Fast division methods">edit</a>]</div> <div class="mw-heading mw-heading3"><h3 id="Newton–Raphson_division">Newton–Raphson division</h3>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=10" title="Edit section: Newton–Raphson division">edit</a>]</div> Newton–Raphson uses <a href="/wiki/Newton%27s_method" title="Newton's method">Newton's method</a> to find the <a href="/wiki/Multiplicative_inverse" title="Multiplicative inverse">reciprocal</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>D</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle D}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}"> and multiply that reciprocal by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"> to find the final quotient <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}">. The steps of Newton–Raphson division are: <ol><li>Calculate an estimate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X_{0}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6381fdad2b9f11954b1fc2db08bbaccf634ededa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.979ex; height:2.509ex;" alt="{\displaystyle X_{0}}"> for the reciprocal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/D}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>D</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1/D}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0ebe16539fe93aaebbd7b4011b3c2ac87fe1b9aa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.249ex; height:2.843ex;" alt="{\displaystyle 1/D}"> of the divisor <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>D</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle D}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}">.</li> <li>Compute successively more accurate estimates <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{1},X_{2},\ldots ,X_{S}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>S</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X_{1},X_{2},\ldots ,X_{S}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/46cf2ec617c833e20a7656b41a2f9168f24a37df" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.386ex; height:2.509ex;" alt="{\displaystyle X_{1},X_{2},\ldots ,X_{S}}"> of the reciprocal. This is where one employs the Newton–Raphson method as such.</li> <li>Compute the quotient by multiplying the dividend by the reciprocal of the divisor: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q=NX_{S}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> <mo>=</mo> <mi>N</mi> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>S</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q=NX_{S}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cf408f63af6025ec07885817f55a6e73f53f6314" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.217ex; height:2.509ex;" alt="{\displaystyle Q=NX_{S}}">.</li></ol> In order to apply Newton's method to find the reciprocal of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>D</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle D}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}">, it is necessary to find a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(X)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(X)}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b884e2d65b3356219702968b6751485fb8f38570" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.068ex; height:2.843ex;" alt="{\displaystyle f(X)}"> that has a zero at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X=1/D}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo>=</mo> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>D</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X=1/D}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5b4dcccbdb6fbe7b3badab65d90fae2a3b67542a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.328ex; height:2.843ex;" alt="{\displaystyle X=1/D}">. The obvious such function is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(X)=DX-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>D</mi> <mi>X</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(X)=DX-1}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6cd146824dc4fa5111538bba41c99ac2da3d55c9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.073ex; height:2.843ex;" alt="{\displaystyle f(X)=DX-1}">, but the Newton–Raphson iteration for this is unhelpful, since it cannot be computed without already knowing the reciprocal of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>D</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle D}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}"> (moreover it attempts to compute the exact reciprocal in one step, rather than allow for iterative improvements). A function that does work is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(X)=(1/X)-D}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>X</mi> <mo stretchy="false">)</mo> <mo>−</mo> <mi>D</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(X)=(1/X)-D}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ed1147f5c4854b44d324c4b83238ea2cdb479b84" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.045ex; height:2.843ex;" alt="{\displaystyle f(X)=(1/X)-D}">, for which the Newton–Raphson iteration gives <dl><dd><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-D \over -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i}),}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>f</mi> <mo stretchy="false">(</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> <mrow> <msup> <mi>f</mi> <mo>′</mo> </msup> <mo stretchy="false">(</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </mfrac> </mrow> <mo>=</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>−</mo> <mi>D</mi> </mrow> <mrow> <mo>−</mo> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <msubsup> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msubsup> </mrow> </mfrac> </mrow> <mo>=</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>+</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <mi>D</mi> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mn>2</mn> <mo>−</mo> <mi>D</mi> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-D \over -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i}),}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/12d0f4546c558ad96c8f68a58aa2b6845dfb156e" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:78.951ex; height:6.843ex;" alt="{\displaystyle X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-D \over -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i}),}"></dd></dl> which can be calculated from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X_{i}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/af4a0955af42beb5f85aa05fb8c07abedc13990d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.724ex; height:2.509ex;" alt="{\displaystyle X_{i}}"> using only multiplication and subtraction, or using two <a href="/wiki/Fused_multiply%E2%80%93add" class="mw-redirect" title="Fused multiply–add">fused multiply–adds</a>. From a computation point of view, the expressions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>+</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <mi>D</mi> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c177500ed6b2494d92b3e2c9146071163f5c340b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.672ex; height:2.843ex;" alt="{\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})}"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i+1}=X_{i}(2-DX_{i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mn>2</mn> <mo>−</mo> <mi>D</mi> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X_{i+1}=X_{i}(2-DX_{i})}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e69468a89d244eca202bc454f97554803b997d41" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.107ex; height:2.843ex;" alt="{\displaystyle X_{i+1}=X_{i}(2-DX_{i})}"> are not equivalent. To obtain a result with a precision of 2n bits while making use of the second expression, one must compute the product between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X_{i}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/af4a0955af42beb5f85aa05fb8c07abedc13990d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.724ex; height:2.509ex;" alt="{\displaystyle X_{i}}"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (2-DX_{i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>2</mn> <mo>−</mo> <mi>D</mi> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (2-DX_{i})}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ff857ba14b90566446aad8257ebae460ca851674" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.46ex; height:2.843ex;" alt="{\displaystyle (2-DX_{i})}"> with double the given precision of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X_{i}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/af4a0955af42beb5f85aa05fb8c07abedc13990d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.724ex; height:2.509ex;" alt="{\displaystyle X_{i}}">(n bits).[<a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed">citation needed</a>] In contrast, the product between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X_{i}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/af4a0955af42beb5f85aa05fb8c07abedc13990d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.724ex; height:2.509ex;" alt="{\displaystyle X_{i}}"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1-DX_{i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <mi>D</mi> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (1-DX_{i})}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0b81a3e0d6031af2c0a8b1aea61d07d8160b9775" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.46ex; height:2.843ex;" alt="{\displaystyle (1-DX_{i})}"> need only be computed with a precision of n bits, because the leading n bits (after the binary point) of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1-DX_{i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <mi>D</mi> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (1-DX_{i})}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0b81a3e0d6031af2c0a8b1aea61d07d8160b9775" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.46ex; height:2.843ex;" alt="{\displaystyle (1-DX_{i})}"> are zeros. If the error is defined as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon _{i}=1-DX_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ε</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>=</mo> <mn>1</mn> <mo>−</mo> <mi>D</mi> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varepsilon _{i}=1-DX_{i}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/98115ffa92ddc012d5ca75557304758ab6693ee8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.633ex; height:2.509ex;" alt="{\displaystyle \varepsilon _{i}=1-DX_{i}}">, then: <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\&=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon _{i}}^{2}.\\\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <msub> <mi>ε</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mtd> <mtd> <mi></mi> <mo>=</mo> <mn>1</mn> <mo>−</mo> <mi>D</mi> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <mn>1</mn> <mo>−</mo> <mi>D</mi> <mo stretchy="false">(</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mn>2</mn> <mo>−</mo> <mi>D</mi> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <mn>1</mn> <mo>−</mo> <mn>2</mn> <mi>D</mi> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>+</mo> <msup> <mi>D</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <msubsup> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msubsup> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <mi>D</mi> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <msup> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>ε</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>.</mo> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\&=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon _{i}}^{2}.\\\end{aligned}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/656efcc4fb42843a4eb2dd7b7c03257fd9eaaeb8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -7.505ex; width:28.754ex; height:16.176ex;" alt="{\displaystyle {\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\&=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon _{i}}^{2}.\\\end{aligned}}}"></dd></dl> This squaring of the error at each iteration step – the so-called <a href="/wiki/Newton%27s_method#Practical_considerations" title="Newton's method">quadratic convergence</a> of Newton–Raphson's method – has the effect that the number of correct digits in the result roughly doubles for every iteration, a property that becomes extremely valuable when the numbers involved have many digits (e.g. in the large integer domain). But it also means that the initial convergence of the method can be comparatively slow, especially if the initial estimate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X_{0}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6381fdad2b9f11954b1fc2db08bbaccf634ededa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.979ex; height:2.509ex;" alt="{\displaystyle X_{0}}"> is poorly chosen. For the subproblem of choosing an initial estimate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X_{0}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6381fdad2b9f11954b1fc2db08bbaccf634ededa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.979ex; height:2.509ex;" alt="{\displaystyle X_{0}}">, it is convenient to apply a bit-shift to the divisor D to scale it so that 0.5 ≤ D ≤ 1; by applying the same bit-shift to the numerator N, one ensures the quotient does not change. Then one could use a linear <a href="/wiki/Approximation" title="Approximation">approximation</a> in the form <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{0}=T_{1}+T_{2}D\approx {\frac {1}{D}}\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mi>D</mi> <mo>≈</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mi>D</mi> </mfrac> </mrow> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X_{0}=T_{1}+T_{2}D\approx {\frac {1}{D}}\,}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4db985c6ce9d8fc75ab34febd821e5fbca1d1a75" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:21.911ex; height:5.176ex;" alt="{\displaystyle X_{0}=T_{1}+T_{2}D\approx {\frac {1}{D}}\,}"></dd></dl> to initialize Newton–Raphson. To minimize the maximum of the absolute value of the error of this approximation on interval <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0.5,1]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">[</mo> <mn>0.5</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle [0.5,1]}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/28b12b2e130f0013fb23a77854afeb5dafbc0d48" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.462ex; height:2.843ex;" alt="{\displaystyle [0.5,1]}">, one should use <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{0}={48 \over 17}-{32 \over 17}D.\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>48</mn> <mn>17</mn> </mfrac> </mrow> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>32</mn> <mn>17</mn> </mfrac> </mrow> <mi>D</mi> <mo>.</mo> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X_{0}={48 \over 17}-{32 \over 17}D.\,}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b695c034f91b7940827b9200e34cfb481881a69a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:18.198ex; height:5.343ex;" alt="{\displaystyle X_{0}={48 \over 17}-{32 \over 17}D.\,}"></dd></dl> The coefficients of the linear approximation are determined as follows. The absolute value of the error is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\varepsilon _{0}|=|1-D(T_{1}+T_{2}D)|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>ε</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo>−</mo> <mi>D</mi> <mo stretchy="false">(</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mi>D</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\varepsilon _{0}|=|1-D(T_{1}+T_{2}D)|}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4921df1e811d82b5555b680faac9cc8ce0783ed1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.148ex; height:2.843ex;" alt="{\displaystyle |\varepsilon _{0}|=|1-D(T_{1}+T_{2}D)|}">. The minimum of the maximum absolute value of the error is determined by the <a href="/wiki/Equioscillation_theorem" title="Equioscillation theorem">Chebyshev equioscillation theorem</a> applied to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(D)=1-D(T_{1}+T_{2}D)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> <mo>−</mo> <mi>D</mi> <mo stretchy="false">(</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mi>D</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(D)=1-D(T_{1}+T_{2}D)}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/efad7ae6687d6ef85bb7eacb788d9a5b5dd482f3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.897ex; height:2.843ex;" alt="{\displaystyle F(D)=1-D(T_{1}+T_{2}D)}">. The local minimum of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(D)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(D)}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7bd590623db38ab20e65c64d9d079cb80025ec5e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.474ex; height:2.843ex;" alt="{\displaystyle F(D)}"> occurs when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F'(D)=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>F</mi> <mo>′</mo> </msup> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F'(D)=0}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2989b2fa88989ae10bc24deeb6ca873c69bc73e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.494ex; height:3.009ex;" alt="{\displaystyle F'(D)=0}">, which has solution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D=-T_{1}/(2T_{2})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>D</mi> <mo>=</mo> <mo>−</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mo stretchy="false">(</mo> <mn>2</mn> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle D=-T_{1}/(2T_{2})}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2d2da42526320389d5f85ea5a0409e6219156ec8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.789ex; height:2.843ex;" alt="{\displaystyle D=-T_{1}/(2T_{2})}">. The function at that minimum must be of opposite sign as the function at the endpoints, namely, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(1/2)=F(1)=-F(-T_{1}/(2T_{2}))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mi>F</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mo>−</mo> <mi>F</mi> <mo stretchy="false">(</mo> <mo>−</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mo stretchy="false">(</mo> <mn>2</mn> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(1/2)=F(1)=-F(-T_{1}/(2T_{2}))}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e25066d71234f90f89d5f67acf8da04d512e3546" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.071ex; height:2.843ex;" alt="{\displaystyle F(1/2)=F(1)=-F(-T_{1}/(2T_{2}))}">. The two equations in the two unknowns have a unique solution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}=48/17}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mn>48</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>17</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}=48/17}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/54019fda2b2bfe5c7aeff0d53a63a256793256fd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.323ex; height:2.843ex;" alt="{\displaystyle T_{1}=48/17}"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}=-32/17}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mo>−</mo> <mn>32</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>17</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}=-32/17}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/81dfca1dfe82420fed289c862973165f7c01444c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.131ex; height:2.843ex;" alt="{\displaystyle T_{2}=-32/17}">, and the maximum error is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F(1)=1/17}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>17</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F(1)=1/17}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a7e26e4f69bf106cbbc1c2c535da24e3e24bfca8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.461ex; height:2.843ex;" alt="{\displaystyle F(1)=1/17}">. Using this approximation, the absolute value of the error of the initial value is less than <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \vert \varepsilon _{0}\vert \leq {1 \over 17}\approx 0.059.\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">|</mo> <msub> <mi>ε</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo fence="false" stretchy="false">|</mo> <mo>≤</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>17</mn> </mfrac> </mrow> <mo>≈</mo> <mn>0.059.</mn> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \vert \varepsilon _{0}\vert \leq {1 \over 17}\approx 0.059.\,}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5d342acb4bb3e5584a85d02da5146106defb53a8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:19.12ex; height:5.343ex;" alt="{\displaystyle \vert \varepsilon _{0}\vert \leq {1 \over 17}\approx 0.059.\,}"></dd></dl> It is possible to generate a polynomial fit of degree larger than 1, computing the coefficients using the <a href="/wiki/Remez_algorithm" title="Remez algorithm">Remez algorithm</a>. The trade-off is that the initial guess requires more computational cycles but hopefully in exchange for fewer iterations of Newton–Raphson. Since for this method the <a href="/wiki/Rate_of_convergence" title="Rate of convergence">convergence</a> is exactly quadratic, it follows that <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S=\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo>=</mo> <mrow> <mo>⌈</mo> <mrow> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>P</mi> <mo>+</mo> <mn>1</mn> </mrow> <mrow> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mn>17</mn> </mrow> </mfrac> </mrow> </mrow> <mo>⌉</mo> </mrow> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S=\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7f189dd98e425c5f32fb0f5842e94ee0979a5ac2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:19.682ex; height:6.176ex;" alt="{\displaystyle S=\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}"></dd></dl> steps are enough to calculate the value up to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P\,}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f60e07ebc2aadee94e4cbbccef71fd9bcf44f5f9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.133ex; height:2.176ex;" alt="{\displaystyle P\,}"> binary places. This evaluates to 3 for IEEE <a href="/wiki/Single_precision" class="mw-redirect" title="Single precision">single precision</a> and 4 for both <a href="/wiki/Double_precision" class="mw-redirect" title="Double precision">double precision</a> and <a href="/wiki/Extended_precision" title="Extended precision">double extended</a> formats. <div class="mw-heading mw-heading4"><h4 id="Pseudocode">Pseudocode</h4>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=11" title="Edit section: Pseudocode">edit</a>]</div> The following computes the quotient of <var style="padding-right: 1px;">N</var> and <var style="padding-right: 1px;">D</var> with a precision of <var style="padding-right: 1px;">P</var> binary places: <pre>Express D as M × 2e where 1 ≤ M < 2 (standard floating point representation) D' := D / 2e+1 // scale between 0.5 and 1, can be performed with bit shift / exponent subtraction N' := N / 2e+1 X := 48/17 − 32/17 × D' // precompute constants with same precision as D repeat <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>⌈</mo> <mrow> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>P</mi> <mo>+</mo> <mn>1</mn> </mrow> <mrow> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mn>17</mn> </mrow> </mfrac> </mrow> </mrow> <mo>⌉</mo> </mrow> <mspace width="thinmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d7b9da88d478a5842f7aa9984da8e5a6aff674eb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:15.085ex; height:6.176ex;" alt="{\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}"> times // can be precomputed based on fixed P X := X + X × (1 - D' × X) end return N' × X </pre> For example, for a double-precision floating-point division, this method uses 10 multiplies, 9 adds, and 2 shifts. <div class="mw-heading mw-heading4"><h4 id="Variant_Newton–Raphson_division">Variant Newton–Raphson division</h4>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=12" title="Edit section: Variant Newton–Raphson division">edit</a>]</div> The Newton-Raphson division method can be modified to be slightly faster as follows. After shifting N and D so that D is in [0.5, 1.0], initialize with <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X:={\frac {140}{33}}+D\cdot \left({\frac {-64}{11}}+D\cdot {\frac {256}{99}}\right).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo>:=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>140</mn> <mn>33</mn> </mfrac> </mrow> <mo>+</mo> <mi>D</mi> <mo>⋅</mo> <mrow> <mo>(</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mo>−</mo> <mn>64</mn> </mrow> <mn>11</mn> </mfrac> </mrow> <mo>+</mo> <mi>D</mi> <mo>⋅</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>256</mn> <mn>99</mn> </mfrac> </mrow> </mrow> <mo>)</mo> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X:={\frac {140}{33}}+D\cdot \left({\frac {-64}{11}}+D\cdot {\frac {256}{99}}\right).}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2c5f4d44a5b460e103036a533cd0e32576c482a2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:36.684ex; height:6.176ex;" alt="{\displaystyle X:={\frac {140}{33}}+D\cdot \left({\frac {-64}{11}}+D\cdot {\frac {256}{99}}\right).}"></dd></dl> This is the best quadratic fit to 1/D and gives an absolute value of the error less than or equal to 1/99. It is chosen to make the error equal to a re-scaled third order <a href="/wiki/Chebyshev_polynomial" class="mw-redirect" title="Chebyshev polynomial">Chebyshev polynomial</a> of the first kind. The coefficients should be pre-calculated and hard-coded. Then in the loop, use an iteration which cubes the error. <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E:=1-D\cdot X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>E</mi> <mo>:=</mo> <mn>1</mn> <mo>−</mo> <mi>D</mi> <mo>⋅</mo> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E:=1-D\cdot X}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/72022eba859136ee8e3f5a225d98083d471cc4fa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:15.107ex; height:2.343ex;" alt="{\displaystyle E:=1-D\cdot X}"></dd> <dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y:=X\cdot E}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Y</mi> <mo>:=</mo> <mi>X</mi> <mo>⋅</mo> <mi>E</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Y:=X\cdot E}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fcd293c88423b35ce2f36adfa7ef9cda13415a01" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.953ex; height:2.176ex;" alt="{\displaystyle Y:=X\cdot E}"></dd> <dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X:=X+Y+Y\cdot E.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo>:=</mo> <mi>X</mi> <mo>+</mo> <mi>Y</mi> <mo>+</mo> <mi>Y</mi> <mo>⋅</mo> <mi>E</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X:=X+Y+Y\cdot E.}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/492114be34dec29aa0b29e52e1951385d5a4c866" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:21.034ex; height:2.343ex;" alt="{\displaystyle X:=X+Y+Y\cdot E.}"></dd></dl> The Y⋅E term is new. If the loop is performed until X agrees with 1/D on its leading P bits, then the number of iterations will be no more than <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\lceil \log _{3}\left({\frac {P+1}{\log _{2}99}}\right)\right\rceil }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>⌈</mo> <mrow> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>⁡</mo> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>P</mi> <mo>+</mo> <mn>1</mn> </mrow> <mrow> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mn>99</mn> </mrow> </mfrac> </mrow> <mo>)</mo> </mrow> </mrow> <mo>⌉</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left\lceil \log _{3}\left({\frac {P+1}{\log _{2}99}}\right)\right\rceil }</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2df6c5e71762d8dd068d5959a48508f347e82594" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:17.732ex; height:6.176ex;" alt="{\displaystyle \left\lceil \log _{3}\left({\frac {P+1}{\log _{2}99}}\right)\right\rceil }"></dd></dl> which is the number of times 99 must be cubed to get to 2P+1. Then <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q:=N\cdot X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> <mo>:=</mo> <mi>N</mi> <mo>⋅</mo> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q:=N\cdot X}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d409d2c9030cd66cfdc35ba4660a3240dd3f7446" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.306ex; height:2.509ex;" alt="{\displaystyle Q:=N\cdot X}"></dd></dl> is the quotient to P bits. Using higher degree polynomials in either the initialization or the iteration results in a degradation of performance because the extra multiplications required would be better spent on doing more iterations. <div class="mw-heading mw-heading3"><h3 id="Goldschmidt_division">Goldschmidt division</h3>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=13" title="Edit section: Goldschmidt division">edit</a>]</div> Goldschmidt division<a href="#cite_note-12">[12]</a> (after Robert Elliott Goldschmidt)<a href="#cite_note-13">[13]</a> uses an iterative process of repeatedly multiplying both the dividend and divisor by a common factor Fi, chosen such that the divisor converges to 1. This causes the dividend to converge to the sought quotient Q: <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>N</mi> <mi>D</mi> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>…</mo> </mrow> </msub> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>…</mo> </mrow> </msub> </mfrac> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}.}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cfafcb018d5743044f980e028fb504f6662d18cf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:19.742ex; height:5.509ex;" alt="{\displaystyle Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}.}"></dd></dl> The steps for Goldschmidt division are: <ol><li>Generate an estimate for the multiplication factor Fi .</li> <li>Multiply the dividend and divisor by Fi .</li> <li>If the divisor is sufficiently close to 1, return the dividend, otherwise, loop to step 1.</li></ol> Assuming N/D has been scaled so that 0 < D < 1, each Fi is based on D: <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{i+1}=2-D_{i}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mn>2</mn> <mo>−</mo> <msub> <mi>D</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{i+1}=2-D_{i}.}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ae7d726be8caa19c6c7946ca355727b4f36cd716" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.867ex; height:2.509ex;" alt="{\displaystyle F_{i+1}=2-D_{i}.}"></dd></dl> Multiplying the dividend and divisor by the factor yields: <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1}}{F_{i+1}}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <msub> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <msub> <mi>D</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mfrac> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <msub> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <msub> <mi>D</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mfrac> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1}}{F_{i+1}}}.}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5113b3bcd50f6ed41c54ddbf3f609c0d9f194e7e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:18.197ex; height:5.843ex;" alt="{\displaystyle {\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1}}{F_{i+1}}}.}"></dd></dl> After a sufficient number k of iterations <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q=N_{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> <mo>=</mo> <msub> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q=N_{k}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4ca08ff8585045f19685c8a0c07755574942e0a5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.892ex; height:2.509ex;" alt="{\displaystyle Q=N_{k}}">. The Goldschmidt method is used in <a href="/wiki/AMD" title="AMD">AMD</a> Athlon CPUs and later models.<a href="#cite_note-14">[14]</a><a href="#cite_note-15">[15]</a> It is also known as Anderson Earle Goldschmidt Powers (AEGP) algorithm and is implemented by various IBM processors.<a href="#cite_note-16">[16]</a><a href="#cite_note-goldschmidt-analysis-17">[17]</a> Although it converges at the same rate as a Newton–Raphson implementation, one advantage of the Goldschmidt method is that the multiplications in the numerator and in the denominator can be done in parallel.<a href="#cite_note-goldschmidt-analysis-17">[17]</a> <div class="mw-heading mw-heading4"><h4 id="Binomial_theorem">Binomial theorem</h4>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=14" title="Edit section: Binomial theorem">edit</a>]</div> The Goldschmidt method can be used with factors that allow simplifications by the <a href="/wiki/Binomial_theorem" title="Binomial theorem">binomial theorem</a>. Assume ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N/D}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>D</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N/D}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d987c29f168f76b3ead5d019d1bd857a2126415c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.15ex; height:2.843ex;" alt="{\displaystyle N/D}">⁠ has been scaled by a <a href="/wiki/Power_of_two" title="Power of two">power of two</a> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D\in \left({\tfrac {1}{2}},1\right]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>D</mi> <mo>∈</mo> <mrow> <mo>(</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mstyle> </mrow> <mo>,</mo> <mn>1</mn> </mrow> <mo>]</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle D\in \left({\tfrac {1}{2}},1\right]}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01936269144731bcdf7908d2b23555ba00659675" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:10.654ex; height:3.509ex;" alt="{\displaystyle D\in \left({\tfrac {1}{2}},1\right]}">. We choose <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D=1-x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>D</mi> <mo>=</mo> <mn>1</mn> <mo>−</mo> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle D=1-x}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/67b31cf2fdf0edc1f9bc2dcff5ed74441df54d7f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.355ex; height:2.343ex;" alt="{\displaystyle D=1-x}"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{i}=1+x^{2^{i}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>=</mo> <mn>1</mn> <mo>+</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F_{i}=1+x^{2^{i}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2a3077ff05d94fcfd311051c75a59abe42b92a25" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.404ex; height:3.343ex;" alt="{\displaystyle F_{i}=1+x^{2^{i}}}">. This yields <dl><dd><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {N}{1-x}}={\frac {N\cdot (1+x)}{1-x^{2}}}={\frac {N\cdot (1+x)\cdot (1+x^{2})}{1-x^{4}}}=\cdots =Q'={\frac {N'=N\cdot (1+x)\cdot (1+x^{2})\cdot \cdot \cdot (1+x^{2^{(n-1)}})}{D'=1-x^{2^{n}}\approx 1}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>N</mi> <mrow> <mn>1</mn> <mo>−</mo> <mi>x</mi> </mrow> </mfrac> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>N</mi> <mo>⋅</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mn>1</mn> <mo>−</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mrow> </mfrac> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>N</mi> <mo>⋅</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>⋅</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> <mrow> <mn>1</mn> <mo>−</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msup> </mrow> </mfrac> </mrow> <mo>=</mo> <mo>⋯</mo> <mo>=</mo> <msup> <mi>Q</mi> <mo>′</mo> </msup> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <msup> <mi>N</mi> <mo>′</mo> </msup> <mo>=</mo> <mi>N</mi> <mo>⋅</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>⋅</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> <mo>⋅</mo> <mo>⋅</mo> <mo>⋅</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> <mrow> <msup> <mi>D</mi> <mo>′</mo> </msup> <mo>=</mo> <mn>1</mn> <mo>−</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mrow> </msup> <mo>≈</mo> <mn>1</mn> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {N}{1-x}}={\frac {N\cdot (1+x)}{1-x^{2}}}={\frac {N\cdot (1+x)\cdot (1+x^{2})}{1-x^{4}}}=\cdots =Q'={\frac {N'=N\cdot (1+x)\cdot (1+x^{2})\cdot \cdot \cdot (1+x^{2^{(n-1)}})}{D'=1-x^{2^{n}}\approx 1}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/09e07ccde63fd8f5e57de96b35bf2b09cae44b21" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:103.636ex; height:6.843ex;" alt="{\displaystyle {\frac {N}{1-x}}={\frac {N\cdot (1+x)}{1-x^{2}}}={\frac {N\cdot (1+x)\cdot (1+x^{2})}{1-x^{4}}}=\cdots =Q'={\frac {N'=N\cdot (1+x)\cdot (1+x^{2})\cdot \cdot \cdot (1+x^{2^{(n-1)}})}{D'=1-x^{2^{n}}\approx 1}}}">.</dd></dl> After n steps <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left(x\in \left[0,{\tfrac {1}{2}}\right)\right)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>(</mo> <mrow> <mi>x</mi> <mo>∈</mo> <mrow> <mo>[</mo> <mrow> <mn>0</mn> <mo>,</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mstyle> </mrow> </mrow> <mo>)</mo> </mrow> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left(x\in \left[0,{\tfrac {1}{2}}\right)\right)}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/66b01b704b7d733e103cdab6e00e694f5b9e1144" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:12.189ex; height:3.509ex;" alt="{\displaystyle \left(x\in \left[0,{\tfrac {1}{2}}\right)\right)}">, the denominator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-x^{2^{n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>−</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1-x^{2^{n}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/809d9f3df6ebfa4fc488add34292fd6f65cbd6bf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.352ex; height:2.843ex;" alt="{\displaystyle 1-x^{2^{n}}}"> can be rounded to 1 with a <a href="/wiki/Relative_error" class="mw-redirect" title="Relative error">relative error</a> <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ε</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <msup> <mi>Q</mi> <mo>′</mo> </msup> <mo>−</mo> <msup> <mi>N</mi> <mo>′</mo> </msup> </mrow> <msup> <mi>Q</mi> <mo>′</mo> </msup> </mfrac> </mrow> <mo>=</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f6a73e13fb93fa34a0422da68ec10c3112bc7842" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:20.855ex; height:6.009ex;" alt="{\displaystyle \varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}}"></dd></dl> which is maximum at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{-2^{n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{-2^{n}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/90d7061184ec120726609bfcbb3dad7dd1f9a57b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.46ex; height:2.676ex;" alt="{\displaystyle 2^{-2^{n}}}"> when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x={\tfrac {1}{2}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x={\tfrac {1}{2}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/21bd3709df6bc6e0e3bcae866eede9d3d97f418c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:6.086ex; height:3.509ex;" alt="{\displaystyle x={\tfrac {1}{2}}}">, thus providing a minimum precision of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8226f30650ee4fe4e640c6d2798127e80e9c160d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}"> binary digits. <div class="mw-heading mw-heading2"><h2 id="Large-integer_methods">Large-integer methods</h2>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=15" title="Edit section: Large-integer methods">edit</a>]</div> Methods designed for hardware implementation generally do not scale to integers with thousands or millions of decimal digits; these frequently occur, for example, in <a href="/wiki/Modular_arithmetic" title="Modular arithmetic">modular</a> reductions in <a href="/wiki/Cryptography" title="Cryptography">cryptography</a>. For these large integers, more efficient division algorithms transform the problem to use a small number of multiplications, which can then be done using an asymptotically efficient <a href="/wiki/Multiplication_algorithm" title="Multiplication algorithm">multiplication algorithm</a> such as the <a href="/wiki/Karatsuba_algorithm" title="Karatsuba algorithm">Karatsuba algorithm</a>, <a href="/wiki/Toom%E2%80%93Cook_multiplication" title="Toom–Cook multiplication">Toom–Cook multiplication</a> or the <a href="/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm" title="Schönhage–Strassen algorithm">Schönhage–Strassen algorithm</a>. The result is that the <a href="/wiki/Computational_complexity" title="Computational complexity">computational complexity</a> of the division is of the same order (up to a multiplicative constant) as that of the multiplication. Examples include reduction to multiplication by <a href="/wiki/Newton%27s_method" title="Newton's method">Newton's method</a> as <a href="#Newton–Raphson_division">described above</a>,<a href="#cite_note-18">[18]</a> as well as the slightly faster <a href="/w/index.php?title=Burnikel-Ziegler_division&action=edit&redlink=1" class="new" title="Burnikel-Ziegler division (page does not exist)">Burnikel-Ziegler division</a>,<a href="#cite_note-19">[19]</a> <a href="/wiki/Barrett_reduction" title="Barrett reduction">Barrett reduction</a> and <a href="/wiki/Montgomery_reduction" class="mw-redirect" title="Montgomery reduction">Montgomery reduction</a> algorithms.<a href="#cite_note-20">[20]</a>[<a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability"><span title="Barrett reduction is usually understood to be the algorithm for computing the remainder that one gets from having precomputed the inverse of the denominator. Rather than providing a solution to the problem of division, it requires that a separate solution is already available! (June 2015)">verification needed</a>] Newton's method is particularly efficient in scenarios where one must divide by the same divisor many times, since after the initial Newton inversion only one (truncated) multiplication is needed for each division. <div class="mw-heading mw-heading2"><h2 id="Division_by_a_constant">Division by a constant</h2>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=16" title="Edit section: Division by a constant">edit</a>]</div> The division by a constant D is equivalent to the multiplication by its <a href="/wiki/Multiplicative_inverse" title="Multiplicative inverse">reciprocal</a>. Since the denominator is constant, so is its reciprocal (1/D). Thus it is possible to compute the value of (1/D) once at compile time, and at run time perform the multiplication N·(1/D) rather than the division N/D. In <a href="/wiki/Floating-point" class="mw-redirect" title="Floating-point">floating-point</a> arithmetic the use of (1/D) presents little problem,<a href="#cite_note-21">[a]</a> but in <a href="/wiki/Integer_(computer_science)" title="Integer (computer science)">integer</a> arithmetic the reciprocal will always evaluate to zero (assuming |D| > 1). It is not necessary to use specifically (1/D); any value (X/Y) that reduces to (1/D) may be used. For example, for division by 3, the factors 1/3, 2/6, 3/9, or 194/582 could be used. Consequently, if Y were a power of two the division step would reduce to a fast right bit shift. The effect of calculating N/D as (N·X)/Y replaces a division with a multiply and a shift. Note that the parentheses are important, as N·(X/Y) will evaluate to zero. However, unless D itself is a power of two, there is no X and Y that satisfies the conditions above. Fortunately, (N·X)/Y gives exactly the same result as N/D in integer arithmetic even when (X/Y) is not exactly equal to 1/D, but "close enough" that the error introduced by the approximation is in the bits that are discarded by the shift operation.<a href="#cite_note-22">[21]</a><a href="#cite_note-23">[22]</a><a href="#cite_note-24">[23]</a> <a href="/wiki/Barrett_reduction" title="Barrett reduction">Barrett reduction</a> uses powers of 2 for the value of Y to make division by Y a simple right shift.<a href="#cite_note-26">[b]</a> As a concrete <a href="/wiki/Fixed-point_arithmetic" title="Fixed-point arithmetic">fixed-point arithmetic</a> example, for 32-bit unsigned integers, division by 3 can be replaced with a multiply by <style data-mw-deduplicate="TemplateStyles:r1214402035">.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}</style>⁠2863311531/233⁠, a multiplication by 2863311531 (<a href="/wiki/Hexadecimal" title="Hexadecimal">hexadecimal</a> 0xAAAAAAAB) followed by a 33 right bit shift. The value of 2863311531 is calculated as <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1214402035">⁠233/3⁠, then rounded up. Likewise, division by 10 can be expressed as a multiplication by 3435973837 (0xCCCCCCCD) followed by division by 235 (or 35 right bit shift).<a href="#cite_note-Hacker's_Delight-27">[25]</a>: p230-234  <a href="/wiki/OEIS" class="mw-redirect" title="OEIS">OEIS</a> provides sequences of the constants for multiplication as <a href="//oeis.org/A346495" class="extiw" title="oeis:A346495">A346495</a> and for the right shift as <a href="//oeis.org/A346496" class="extiw" title="oeis:A346496">A346496</a>. For general x-bit unsigned integer division where the divisor D is not a power of 2, the following identity converts the division into two x-bit addition/subtraction, one x-bit by x-bit multiplication (where only the upper half of the result is used) and several shifts, after precomputing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=x+\lceil \log _{2}{D}\rceil }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>=</mo> <mi>x</mi> <mo>+</mo> <mo fence="false" stretchy="false">⌈</mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>D</mi> </mrow> <mo fence="false" stretchy="false">⌉</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k=x+\lceil \log _{2}{D}\rceil }</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9338c4c89623bd386dbe012c1357a2254506eb9f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.882ex; height:2.843ex;" alt="{\displaystyle k=x+\lceil \log _{2}{D}\rceil }"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>=</mo> <mrow> <mo>⌈</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mi>D</mi> </mfrac> </mrow> <mo>⌉</mo> </mrow> <mo>−</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1698b05b8d70d452d2517ed9b8899fd8fb3d5d22" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:15.301ex; height:6.343ex;" alt="{\displaystyle a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}}">: <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {N-b}{2}}\right\rfloor +b}{2^{k-x-1}}}\right\rfloor {\text{ where }}b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>⌊</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>N</mi> <mi>D</mi> </mfrac> </mrow> <mo>⌋</mo> </mrow> <mo>=</mo> <mrow> <mo>⌊</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mrow> <mo>⌊</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>N</mi> <mo>−</mo> <mi>b</mi> </mrow> <mn>2</mn> </mfrac> </mrow> <mo>⌋</mo> </mrow> <mo>+</mo> <mi>b</mi> </mrow> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>−</mo> <mi>x</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mfrac> </mrow> <mo>⌋</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mtext> where </mtext> </mrow> <mi>b</mi> <mo>=</mo> <mrow> <mo>⌊</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>N</mi> <mi>a</mi> </mrow> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msup> </mfrac> </mrow> <mo>⌋</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {N-b}{2}}\right\rfloor +b}{2^{k-x-1}}}\right\rfloor {\text{ where }}b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor }</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bfb5d8ba6fd1c53ffdfa6f2731779bf677b53be6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.505ex; width:41.649ex; height:10.176ex;" alt="{\displaystyle \left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {N-b}{2}}\right\rfloor +b}{2^{k-x-1}}}\right\rfloor {\text{ where }}b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor }"></dd></dl> In some cases, division by a constant can be accomplished in even less time by converting the "multiply by a constant" into a <a href="/wiki/Multiplication_algorithm#Shift_and_add" title="Multiplication algorithm">series of shifts and adds or subtracts</a>.<a href="#cite_note-28">[26]</a> Of particular interest is division by 10, for which the exact quotient is obtained, with remainder if required.<a href="#cite_note-29">[27]</a> <div class="mw-heading mw-heading2"><h2 id="Rounding_error">Rounding error</h2>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=17" title="Edit section: Rounding error">edit</a>]</div> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-Expand_section plainlinks metadata ambox mbox-small-left ambox-content" role="presentation"><tbody><tr><td class="mbox-image"><a href="/wiki/File:Wiki_letter_w_cropped.svg" class="mw-file-description"><img alt="[icon]" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png" decoding="async" width="20" height="14" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/30px-Wiki_letter_w_cropped.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/40px-Wiki_letter_w_cropped.svg.png 2x" data-file-width="44" data-file-height="31" /></a></td><td class="mbox-text"><div class="mbox-text-span">This section needs expansion. You can help by <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Division_algorithm&action=edit&section=">adding to it</a>. (September 2012)</div></td></tr></tbody></table> When a division operation is performed, the exact <a href="/wiki/Quotient" title="Quotient">quotient</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06809d64fa7c817ffc7e323f85997f783dbdf71d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}"> and <a href="/wiki/Remainder" title="Remainder">remainder</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}"> are approximated to fit within the computer’s precision limits. The Division Algorithm states: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [a=bq+r]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">[</mo> <mi>a</mi> <mo>=</mo> <mi>b</mi> <mi>q</mi> <mo>+</mo> <mi>r</mi> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle [a=bq+r]}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/082dbab89cb70659e15587e2aae1cbcb37f37dcc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.578ex; height:2.843ex;" alt="{\displaystyle [a=bq+r]}"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq r<|b|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>0</mn> <mo>≤</mo> <mi>r</mi> <mo><</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 0\leq r<|b|}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d3fc64c6bf589852efd9096b83210cc89be7bdb2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.699ex; height:2.843ex;" alt="{\displaystyle 0\leq r<|b|}">. In <a href="/wiki/Floating-point_arithmetic" title="Floating-point arithmetic">floating-point arithmetic</a>, the quotient <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06809d64fa7c817ffc7e323f85997f783dbdf71d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}"> is represented as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tilde {q}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>q</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tilde {q}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9799511dfd2e51ec2827f6cdab2b75ed8cd1595e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.377ex; height:2.509ex;" alt="{\displaystyle {\tilde {q}}}"> and the remainder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}"> as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tilde {r}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>r</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tilde {r}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/85962e2c63f61329fa0089221292e8e519c9fe2c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.292ex; height:2.176ex;" alt="{\displaystyle {\tilde {r}}}">, introducing <a href="/wiki/Round-off_error" title="Round-off error">rounding errors</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon _{q}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ϵ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>q</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \epsilon _{q}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0f90289afd4033c580eea31973595ee8402ddb45" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.933ex; height:2.343ex;" alt="{\displaystyle \epsilon _{q}}"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon _{q}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ϵ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>q</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \epsilon _{q}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0f90289afd4033c580eea31973595ee8402ddb45" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.933ex; height:2.343ex;" alt="{\displaystyle \epsilon _{q}}"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon _{r}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ϵ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \epsilon _{r}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7ff36e034ac43c6b67b68ed1b87ca7a5b4e42f9b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.918ex; height:2.009ex;" alt="{\displaystyle \epsilon _{r}}">: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [{\tilde {q}}=q+\epsilon _{q}][{\tilde {r}}=r+\epsilon _{r}]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">[</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>q</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mo>=</mo> <mi>q</mi> <mo>+</mo> <msub> <mi>ϵ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>q</mi> </mrow> </msub> <mo stretchy="false">]</mo> <mo stretchy="false">[</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>r</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mo>=</mo> <mi>r</mi> <mo>+</mo> <msub> <mi>ϵ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> </mrow> </msub> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle [{\tilde {q}}=q+\epsilon _{q}][{\tilde {r}}=r+\epsilon _{r}]}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a8d5bc6d54afa2acff2eacc1355cb4dd75829038" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:23.103ex; height:3.009ex;" alt="{\displaystyle [{\tilde {q}}=q+\epsilon _{q}][{\tilde {r}}=r+\epsilon _{r}]}"> This rounding causes a small error, which can propagate and accumulate through subsequent calculations. Such errors are particularly pronounced in iterative processes and when subtracting nearly equal values - is told <a href="/wiki/Catastrophic_cancellation" title="Catastrophic cancellation">loss of significance</a>. To mitigate these errors, techniques such as the use of <a href="/wiki/Guard_digit" title="Guard digit">guard digits</a> or <a href="/w/index.php?title=Higher_precision_arithmetic&action=edit&redlink=1" class="new" title="Higher precision arithmetic (page does not exist)">higher precision arithmetic</a> are employed.<a href="#cite_note-30">[28]</a><a href="#cite_note-31">[29]</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Further information: <a href="/wiki/Floating_point" class="mw-redirect" title="Floating point">Floating point</a></div> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=18" title="Edit section: See also">edit</a>]</div> <ul><li><a href="/wiki/Galley_division" title="Galley division">Galley division</a></li> <li><a href="/wiki/Multiplication_algorithm" title="Multiplication algorithm">Multiplication algorithm</a></li> <li><a href="/wiki/Pentium_FDIV_bug" title="Pentium FDIV bug">Pentium FDIV bug</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=19" title="Edit section: Notes">edit</a>]</div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist reflist-lower-alpha"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-21"><a href="#cite_ref-21">^</a> Despite how "little" problem the optimization causes, this reciprocal optimization is still usually hidden behind a "fast math" flag in modern <a href="/wiki/Compiler" title="Compiler">compilers</a> as it is inexact. </li> <li id="cite_note-26"><a href="#cite_ref-26">^</a> Modern <a href="/wiki/Compilers" class="mw-redirect" title="Compilers">compilers</a> commonly perform this integer multiply-and-shift optimization; for a constant only known at run-time, however, the program must implement the optimization itself.<a href="#cite_note-25">[24]</a> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=20" title="Edit section: References">edit</a>]</div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239543626"><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-1"><a href="#cite_ref-1">^</a> <style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFRodeheffer2008" class="citation techreport cs1">Rodeheffer, Thomas L. (2008-08-26). <a rel="nofollow" class="external text" href="https://www.microsoft.com/en-us/research/wp-content/uploads/2008/08/tr-2008-141.pdf">Software Integer Division</a> (PDF) (Technical report). Microsoft Research, Silicon Valley.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=report&rft.btitle=Software+Integer+Division&rft.pub=Microsoft+Research%2C+Silicon+Valley&rft.date=2008-08-26&rft.aulast=Rodeheffer&rft.aufirst=Thomas+L.&rft_id=https%3A%2F%2Fwww.microsoft.com%2Fen-us%2Fresearch%2Fwp-content%2Fuploads%2F2008%2F08%2Ftr-2008-141.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-2"><a href="#cite_ref-2">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMorrisIniewski2017" class="citation book cs1">Morris, James E.; Iniewski, Krzysztof (2017-11-22). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=wAhEDwAAQBAJ&q=restoring+division+fixed-point+fractional+numbers&pg=PA243">Nanoelectronic Device Applications Handbook</a>. CRC Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-351-83197-0" title="Special:BookSources/978-1-351-83197-0"><bdi>978-1-351-83197-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Nanoelectronic+Device+Applications+Handbook&rft.pub=CRC+Press&rft.date=2017-11-22&rft.isbn=978-1-351-83197-0&rft.aulast=Morris&rft.aufirst=James+E.&rft.au=Iniewski%2C+Krzysztof&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DwAhEDwAAQBAJ%26q%3Drestoring%2Bdivision%2Bfixed-point%2Bfractional%2Bnumbers%26pg%3DPA243&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-3"><a href="#cite_ref-3">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFShaw1950" class="citation journal cs1">Shaw, Robert F. (1950). <a rel="nofollow" class="external text" href="http://aip.scitation.org/doi/10.1063/1.1745692">"Arithmetic Operations in a Binary Computer"</a>. Review of Scientific Instruments. 21 (8): 690. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1950RScI...21..687S">1950RScI...21..687S</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1063%2F1.1745692">10.1063/1.1745692</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0034-6748">0034-6748</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220228182241/https://aip.scitation.org/doi/10.1063/1.1745692">Archived</a> from the original on 2022-02-28. Retrieved 2022-02-28.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Review+of+Scientific+Instruments&rft.atitle=Arithmetic+Operations+in+a+Binary+Computer&rft.volume=21&rft.issue=8&rft.pages=690&rft.date=1950&rft.issn=0034-6748&rft_id=info%3Adoi%2F10.1063%2F1.1745692&rft_id=info%3Abibcode%2F1950RScI...21..687S&rft.aulast=Shaw&rft.aufirst=Robert+F.&rft_id=http%3A%2F%2Faip.scitation.org%2Fdoi%2F10.1063%2F1.1745692&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-4"><a href="#cite_ref-4">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFlynn" class="citation web cs1">Flynn. <a rel="nofollow" class="external text" href="https://web.stanford.edu/class/ee486/doc/chap5.pdf">"Stanford EE486 (Advanced Computer Arithmetic Division) – Chapter 5 Handout (Division)"</a> (PDF). Stanford University. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220418044630/http://web.stanford.edu/class/ee486/doc/chap5.pdf">Archived</a> (PDF) from the original on 2022-04-18. Retrieved 2019-06-24.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Stanford+University&rft.atitle=Stanford+EE486+%28Advanced+Computer+Arithmetic+Division%29+%26ndash%3B%26%2332%3B+Chapter+5+Handout+%28Division%29&rft.au=Flynn&rft_id=https%3A%2F%2Fweb.stanford.edu%2Fclass%2Fee486%2Fdoc%2Fchap5.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-5"><a href="#cite_ref-5">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHarrisObermanHorowitz1998" class="citation techreport cs1">Harris, David L.; Oberman, Stuart F.; Horowitz, Mark A. (9 September 1998). <a rel="nofollow" class="external text" href="http://pages.hmc.edu/harris/research/srtlong.pdf">SRT Division: Architectures, Models, and Implementations</a> (PDF) (Technical report). Stanford University. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20161224030439/http://pages.hmc.edu/harris/research/srtlong.pdf">Archived</a> (PDF) from the original on 24 December 2016. Retrieved 23 December 2016.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=report&rft.btitle=SRT+Division%3A+Architectures%2C+Models%2C+and+Implementations&rft.pub=Stanford+University&rft.date=1998-09-09&rft.aulast=Harris&rft.aufirst=David+L.&rft.au=Oberman%2C+Stuart+F.&rft.au=Horowitz%2C+Mark+A.&rft_id=http%3A%2F%2Fpages.hmc.edu%2Fharris%2Fresearch%2Fsrtlong.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-6"><a href="#cite_ref-6">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMcCannPippenger2005" class="citation journal cs1">McCann, Mark; Pippenger, Nicholas (2005). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/614875">"SRT Division Algorithms as Dynamical Systems"</a>. SIAM Journal on Computing. 34 (6): 1279–1301. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.6993">10.1.1.72.6993</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS009753970444106X">10.1137/S009753970444106X</a>. <a href="/wiki/Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2429%2F12179">2429/12179</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220824213238/https://ieeexplore.ieee.org/document/614875">Archived</a> from the original on 2022-08-24. Retrieved 2022-08-24.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=SRT+Division+Algorithms+as+Dynamical+Systems&rft.volume=34&rft.issue=6&rft.pages=1279-1301&rft.date=2005&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.72.6993%23id-name%3DCiteSeerX&rft_id=info%3Ahdl%2F2429%2F12179&rft_id=info%3Adoi%2F10.1137%2FS009753970444106X&rft.aulast=McCann&rft.aufirst=Mark&rft.au=Pippenger%2C+Nicholas&rft_id=https%3A%2F%2Fieeexplore.ieee.org%2Fdocument%2F614875&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-7"><a href="#cite_ref-7">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCockeSweeney1957" class="citation cs2">Cocke, John; Sweeney, D.W. (11 February 1957), <a rel="nofollow" class="external text" href="https://www.computerhistory.org/collections/catalog/102632302">High speed arithmetic in a parallel device</a> (Company Memo), IBM, p. 20, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220824212341/https://www.computerhistory.org/collections/catalog/102632302">archived</a> from the original on 24 August 2022, retrieved 24 August 2022</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=High+speed+arithmetic+in+a+parallel+device&rft.place=IBM&rft.pages=20&rft.date=1957-02-11&rft.aulast=Cocke&rft.aufirst=John&rft.au=Sweeney%2C+D.W.&rft_id=https%3A%2F%2Fwww.computerhistory.org%2Fcollections%2Fcatalog%2F102632302&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"><code class="cs1-code">{{<a href="/wiki/Template:Citation" title="Template:Citation">citation</a>}}</code>: CS1 maint: location missing publisher (<a href="/wiki/Category:CS1_maint:_location_missing_publisher" title="Category:CS1 maint: location missing publisher">link</a>) </li> <li id="cite_note-8"><a href="#cite_ref-8">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRobertson1958" class="citation journal cs1">Robertson, James (1958-09-01). <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/5222579">"A New Class of Digital Division Methods"</a>. IRE Transactions on Electronic Computers. EC-7 (3). IEEE: 218–222. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTEC.1958.5222579">10.1109/TEC.1958.5222579</a>. <a href="/wiki/Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2027%2Fuiuo.ark%3A%2F13960%2Ft0gt7529c">2027/uiuo.ark:/13960/t0gt7529c</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220824213239/https://ieeexplore.ieee.org/document/5222579">Archived</a> from the original on 2022-08-24. Retrieved 2022-08-24.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IRE+Transactions+on+Electronic+Computers&rft.atitle=A+New+Class+of+Digital+Division+Methods&rft.volume=EC-7&rft.issue=3&rft.pages=218-222&rft.date=1958-09-01&rft_id=info%3Ahdl%2F2027%2Fuiuo.ark%3A%2F13960%2Ft0gt7529c&rft_id=info%3Adoi%2F10.1109%2FTEC.1958.5222579&rft.aulast=Robertson&rft.aufirst=James&rft_id=https%3A%2F%2Fieeexplore.ieee.org%2Fdocument%2F5222579&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-9"><a href="#cite_ref-9">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTocher1958" class="citation journal cs1">Tocher, K.D. (1958-01-01). <a rel="nofollow" class="external text" href="https://academic.oup.com/qjmam/article-abstract/11/3/364/1883426">"Techniques of Multiplication and Division for Automatic Binary Computers"</a>. The Quarterly Journal of Mechanics and Applied Mathematics. 11 (3): 364–384. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fqjmam%2F11.3.364">10.1093/qjmam/11.3.364</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220824214400/https://academic.oup.com/qjmam/article-abstract/11/3/364/1883426">Archived</a> from the original on 2022-08-24. Retrieved 2022-08-24.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=The+Quarterly+Journal+of+Mechanics+and+Applied+Mathematics&rft.atitle=Techniques+of+Multiplication+and+Division+for+Automatic+Binary+Computers&rft.volume=11&rft.issue=3&rft.pages=364-384&rft.date=1958-01-01&rft_id=info%3Adoi%2F10.1093%2Fqjmam%2F11.3.364&rft.aulast=Tocher&rft.aufirst=K.D.&rft_id=https%3A%2F%2Facademic.oup.com%2Fqjmam%2Farticle-abstract%2F11%2F3%2F364%2F1883426&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-10"><a href="#cite_ref-10">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.intel.com/support/processors/pentium/sb/cs-012997.htm">"Statistical Analysis of Floating Point Flaw"</a>. Intel Corporation. 1994. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20131023060231/http://www.intel.com/support/processors/pentium/sb/cs-012997.htm">Archived</a> from the original on 23 October 2013. Retrieved 22 October 2013.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Statistical+Analysis+of+Floating+Point+Flaw&rft.pub=Intel+Corporation&rft.date=1994&rft_id=http%3A%2F%2Fwww.intel.com%2Fsupport%2Fprocessors%2Fpentium%2Fsb%2Fcs-012997.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-11"><a href="#cite_ref-11">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFObermanFlynn1995" class="citation techreport cs1">Oberman, Stuart F.; Flynn, Michael J. (July 1995). <a rel="nofollow" class="external text" href="http://i.stanford.edu/pub/cstr/reports/csl/tr/95/675/CSL-TR-95-675.pdf">An Analysis of Division Algorithms and Implementations</a> (PDF) (Technical report). Stanford University. CSL-TR-95-675. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170517133304/http://i.stanford.edu/pub/cstr/reports/csl/tr/95/675/CSL-TR-95-675.pdf">Archived</a> (PDF) from the original on 2017-05-17. Retrieved 2016-12-23.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=report&rft.btitle=An+Analysis+of+Division+Algorithms+and+Implementations&rft.pub=Stanford+University&rft.date=1995-07&rft.aulast=Oberman&rft.aufirst=Stuart+F.&rft.au=Flynn%2C+Michael+J.&rft_id=http%3A%2F%2Fi.stanford.edu%2Fpub%2Fcstr%2Freports%2Fcsl%2Ftr%2F95%2F675%2FCSL-TR-95-675.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-12"><a href="#cite_ref-12">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGoldschmidt1964" class="citation thesis cs1">Goldschmidt, Robert E. (1964). <a rel="nofollow" class="external text" href="http://dspace.mit.edu/bitstream/handle/1721.1/11113/34136725-MIT.pdf">Applications of Division by Convergence</a> (PDF) (Thesis). M.Sc. dissertation. M.I.T. <a href="/wiki/OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/34136725">34136725</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20151210223340/http://dspace.mit.edu/bitstream/handle/1721.1/11113/34136725-MIT.pdf">Archived</a> (PDF) from the original on 2015-12-10. Retrieved 2015-09-15.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Applications+of+Division+by+Convergence&rft.inst=M.I.T.&rft.date=1964&rft_id=info%3Aoclcnum%2F34136725&rft.aulast=Goldschmidt&rft.aufirst=Robert+E.&rft_id=http%3A%2F%2Fdspace.mit.edu%2Fbitstream%2Fhandle%2F1721.1%2F11113%2F34136725-MIT.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-13"><a href="#cite_ref-13">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation journal cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20180718114413/https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5392026">"Authors"</a>. IBM Journal of Research and Development. 11: 125–127. 1967. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1147%2Frd.111.0125">10.1147/rd.111.0125</a>. Archived from <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/5392026">the original</a> on 18 July 2018.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IBM+Journal+of+Research+and+Development&rft.atitle=Authors&rft.volume=11&rft.pages=125-127&rft.date=1967&rft_id=info%3Adoi%2F10.1147%2Frd.111.0125&rft_id=https%3A%2F%2Fieeexplore.ieee.org%2Fdocument%2F5392026&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-14"><a href="#cite_ref-14">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFOberman1999" class="citation book cs1">Oberman, Stuart F. (1999). <a rel="nofollow" class="external text" href="http://www.acsel-lab.com/arithmetic/arith14/papers/ARITH14_Oberman.pdf">"Floating point division and square root algorithms and implementation in the AMD-K7 Microprocessor"</a> (PDF). Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No.99CB36336). pp. 106–115. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FARITH.1999.762835">10.1109/ARITH.1999.762835</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-7695-0116-8" title="Special:BookSources/0-7695-0116-8"><bdi>0-7695-0116-8</bdi></a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:12793819">12793819</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20151129095846/http://www.acsel-lab.com/arithmetic/arith14/papers/ARITH14_Oberman.pdf">Archived</a> (PDF) from the original on 2015-11-29. Retrieved 2015-09-15.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Floating+point+division+and+square+root+algorithms+and+implementation+in+the+AMD-K7+Microprocessor&rft.btitle=Proceedings+14th+IEEE+Symposium+on+Computer+Arithmetic+%28Cat.+No.99CB36336%29&rft.pages=106-115&rft.date=1999&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A12793819%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1109%2FARITH.1999.762835&rft.isbn=0-7695-0116-8&rft.aulast=Oberman&rft.aufirst=Stuart+F.&rft_id=http%3A%2F%2Fwww.acsel-lab.com%2Farithmetic%2Farith14%2Fpapers%2FARITH14_Oberman.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-15"><a href="#cite_ref-15">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSoderquistLeeser1997" class="citation journal cs1">Soderquist, Peter; Leeser, Miriam (July–August 1997). <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/2511700">"Division and Square Root: Choosing the Right Implementation"</a>. IEEE Micro. 17 (4): 56–66. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F40.612224">10.1109/40.612224</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IEEE+Micro&rft.atitle=Division+and+Square+Root%3A+Choosing+the+Right+Implementation&rft.volume=17&rft.issue=4&rft.pages=56-66&rft.date=1997-07%2F1997-08&rft_id=info%3Adoi%2F10.1109%2F40.612224&rft.aulast=Soderquist&rft.aufirst=Peter&rft.au=Leeser%2C+Miriam&rft_id=https%3A%2F%2Fwww.researchgate.net%2Fpublication%2F2511700&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-16"><a href="#cite_ref-16">^</a> S. F. Anderson, J. G. Earle, R. E. Goldschmidt, D. M. Powers. The IBM 360/370 model 91: floating-point execution unit, <a href="/wiki/IBM_Journal_of_Research_and_Development" title="IBM Journal of Research and Development">IBM Journal of Research and Development</a>, January 1997 </li> <li id="cite_note-goldschmidt-analysis-17">^ <a href="#cite_ref-goldschmidt-analysis_17-0">a</a> <a href="#cite_ref-goldschmidt-analysis_17-1">b</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGuyPeterFerguson2005" class="citation journal cs1">Guy, Even; Peter, Siedel; Ferguson, Warren (1 February 2005). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2004.08.004">"A parametric error analysis of Goldschmidt's division algorithm"</a>. Journal of Computer and System Sciences. 70 (1): 118–139. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2004.08.004">10.1016/j.jcss.2004.08.004</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Computer+and+System+Sciences&rft.atitle=A+parametric+error+analysis+of+Goldschmidt%27s+division+algorithm&rft.volume=70&rft.issue=1&rft.pages=118-139&rft.date=2005-02-01&rft_id=info%3Adoi%2F10.1016%2Fj.jcss.2004.08.004&rft.aulast=Guy&rft.aufirst=Even&rft.au=Peter%2C+Siedel&rft.au=Ferguson%2C+Warren&rft_id=https%3A%2F%2Fdoi.org%2F10.1016%252Fj.jcss.2004.08.004&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-18"><a href="#cite_ref-18">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHasselström2003" class="citation thesis cs1">Hasselström, Karl (2003). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170708221722/https://static1.squarespace.com/static/5692a9ad7086d724272eb00a/t/5692dbe6b204d50df79e577f/1452465127528/masters-thesis.pdf">Fast Division of Large Integers: A Comparison of Algorithms</a> (PDF) (M.Sc. in Computer Science thesis). Royal Institute of Technology. Archived from <a rel="nofollow" class="external text" href="https://treskal.com/s/masters-thesis.pdf">the original</a> (PDF) on 8 July 2017. Retrieved 2017-07-08.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Fast+Division+of+Large+Integers%3A+A+Comparison+of+Algorithms&rft.degree=M.Sc.+in+Computer+Science&rft.inst=Royal+Institute+of+Technology&rft.date=2003&rft.aulast=Hasselstr%C3%B6m&rft.aufirst=Karl&rft_id=https%3A%2F%2Ftreskal.com%2Fs%2Fmasters-thesis.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-19"><a href="#cite_ref-19">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJoachim_Ziegler1998" class="citation cs2">Joachim Ziegler, Christoph Burnikel (1998), <a rel="nofollow" class="external text" href="https://domino.mpi-inf.mpg.de/internet/reports.nsf/efc044f1568a0058c125642e0064c817/a8cfefdd1ac031bbc125669b00493127/$FILE/MPI-I-98-1-022.ps">Fast Recursive Division</a>, Max-Planck-Institut für Informatik, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110426221250/http://domino.mpi-inf.mpg.de/internet/reports.nsf/efc044f1568a0058c125642e0064c817/a8cfefdd1ac031bbc125669b00493127/$FILE/MPI-I-98-1-022.ps">archived</a> from the original on 2011-04-26, retrieved 2021-09-10</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Fast+Recursive+Division&rft.place=Max-Planck-Institut+f%C3%BCr+Informatik&rft.date=1998&rft.aulast=Joachim+Ziegler&rft.aufirst=Christoph+Burnikel&rft_id=https%3A%2F%2Fdomino.mpi-inf.mpg.de%2Finternet%2Freports.nsf%2Fefc044f1568a0058c125642e0064c817%2Fa8cfefdd1ac031bbc125669b00493127%2F%24FILE%2FMPI-I-98-1-022.ps&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"><code class="cs1-code">{{<a href="/wiki/Template:Citation" title="Template:Citation">citation</a>}}</code>: CS1 maint: location missing publisher (<a href="/wiki/Category:CS1_maint:_location_missing_publisher" title="Category:CS1 maint: location missing publisher">link</a>) </li> <li id="cite_note-20"><a href="#cite_ref-20">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBarrett1987" class="citation conference cs1">Barrett, Paul (1987). <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=36688">"Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor"</a>. Proceedings on Advances in cryptology---CRYPTO '86. London, UK: Springer-Verlag. pp. 311–323. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-387-18047-8" title="Special:BookSources/0-387-18047-8"><bdi>0-387-18047-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=Implementing+the+Rivest+Shamir+and+Adleman+public+key+encryption+algorithm+on+a+standard+digital+signal+processor&rft.btitle=Proceedings+on+Advances+in+cryptology---CRYPTO+%2786&rft.place=London%2C+UK&rft.pages=311-323&rft.pub=Springer-Verlag&rft.date=1987&rft.isbn=0-387-18047-8&rft.aulast=Barrett&rft.aufirst=Paul&rft_id=http%3A%2F%2Fportal.acm.org%2Fcitation.cfm%3Fid%3D36688&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-22"><a href="#cite_ref-22">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGranlundMontgomery1994" class="citation journal cs1">Granlund, Torbjörn; Montgomery, Peter L. (June 1994). <a rel="nofollow" class="external text" href="http://gmplib.org/~tege/divcnst-pldi94.pdf">"Division by Invariant Integers using Multiplication"</a> (PDF). SIGPLAN Notices. 29 (6): 61–72. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.2556">10.1.1.1.2556</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F773473.178249">10.1145/773473.178249</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20190606211506/https://gmplib.org/~tege/divcnst-pldi94.pdf">Archived</a> (PDF) from the original on 2019-06-06. Retrieved 2015-12-08.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIGPLAN+Notices&rft.atitle=Division+by+Invariant+Integers+using+Multiplication&rft.volume=29&rft.issue=6&rft.pages=61-72&rft.date=1994-06&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.1.2556%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1145%2F773473.178249&rft.aulast=Granlund&rft.aufirst=Torbj%C3%B6rn&rft.au=Montgomery%2C+Peter+L.&rft_id=http%3A%2F%2Fgmplib.org%2F~tege%2Fdivcnst-pldi94.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-23"><a href="#cite_ref-23">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMöllerGranlund2011" class="citation journal cs1">Möller, Niels; Granlund, Torbjörn (February 2011). <a rel="nofollow" class="external text" href="http://gmplib.org/~tege/division-paper.pdf">"Improved Division by Invariant Integers"</a> (PDF). IEEE Transactions on Computers. 60 (2): 165–175. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTC.2010.143">10.1109/TC.2010.143</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13347152">13347152</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20151222160554/https://gmplib.org/~tege/division-paper.pdf">Archived</a> (PDF) from the original on 2015-12-22. Retrieved 2015-12-08.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IEEE+Transactions+on+Computers&rft.atitle=Improved+Division+by+Invariant+Integers&rft.volume=60&rft.issue=2&rft.pages=165-175&rft.date=2011-02&rft_id=info%3Adoi%2F10.1109%2FTC.2010.143&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A13347152%23id-name%3DS2CID&rft.aulast=M%C3%B6ller&rft.aufirst=Niels&rft.au=Granlund%2C+Torbj%C3%B6rn&rft_id=http%3A%2F%2Fgmplib.org%2F~tege%2Fdivision-paper.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-24"><a href="#cite_ref-24">^</a> ridiculous_fish. <a rel="nofollow" class="external text" href="http://ridiculousfish.com/files/faster_unsigned_division_by_constants.pdf">"Labor of Division (Episode III): Faster Unsigned Division by Constants"</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220108225258/http://ridiculousfish.com/files/faster_unsigned_division_by_constants.pdf">Archived</a> 2022-01-08 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a>. 2011. </li> <li id="cite_note-25"><a href="#cite_ref-25">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFridiculous_fish" class="citation web cs1">ridiculous_fish. <a rel="nofollow" class="external text" href="https://libdivide.com/">"libdivide, optimized integer division"</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20211123015446/https://libdivide.com/">Archived</a> from the original on 23 November 2021. Retrieved 6 July 2021.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=libdivide%2C+optimized+integer+division&rft.au=ridiculous_fish&rft_id=https%3A%2F%2Flibdivide.com%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-Hacker's_Delight-27"><a href="#cite_ref-Hacker's_Delight_27-0">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWarren_Jr.2013" class="citation book cs1">Warren Jr., Henry S. (2013). <a href="/wiki/Hacker%27s_Delight" title="Hacker's Delight">Hacker's Delight</a> (2 ed.). <a href="/wiki/Addison_Wesley" class="mw-redirect" title="Addison Wesley">Addison Wesley</a> - <a href="/wiki/Pearson_Education,_Inc." class="mw-redirect" title="Pearson Education, Inc.">Pearson Education, Inc.</a> <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-321-84268-8" title="Special:BookSources/978-0-321-84268-8"><bdi>978-0-321-84268-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Hacker%27s+Delight&rft.edition=2&rft.pub=Addison+Wesley+-+Pearson+Education%2C+Inc.&rft.date=2013&rft.isbn=978-0-321-84268-8&rft.aulast=Warren+Jr.&rft.aufirst=Henry+S.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-28"><a href="#cite_ref-28">^</a> LaBudde, Robert A.; Golovchenko, Nikolai; Newton, James; and Parker, David; <a rel="nofollow" class="external text" href="http://techref.massmind.org/techref/method/math/divconst.htm">Massmind: "Binary Division by a Constant"</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220109215748/http://techref.massmind.org/techref/method/math/divconst.htm">Archived</a> 2022-01-09 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a> </li> <li id="cite_note-29"><a href="#cite_ref-29">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFVowels1992" class="citation journal cs1">Vowels, R. A. (1992). "Division by 10". Australian Computer Journal. 24 (3): 81–85.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Australian+Computer+Journal&rft.atitle=Division+by+10&rft.volume=24&rft.issue=3&rft.pages=81-85&rft.date=1992&rft.aulast=Vowels&rft.aufirst=R.+A.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-30"><a href="#cite_ref-30">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFL._Popyack2000" class="citation journal cs1">L. Popyack, Jeffrey (June 2000). <a rel="nofollow" class="external text" href="https://www.cs.drexel.edu/~popyack/Courses/CSP/Fa17/extras/Rounding/index.html">"Rounding Error"</a>. <a href="/wiki/Drexel_University" title="Drexel University">Drexel University</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Drexel+University&rft.atitle=Rounding+Error&rft.date=2000-06&rft.aulast=L.+Popyack&rft.aufirst=Jeffrey&rft_id=https%3A%2F%2Fwww.cs.drexel.edu%2F~popyack%2FCourses%2FCSP%2FFa17%2Fextras%2FRounding%2Findex.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> <li id="cite_note-31"><a href="#cite_ref-31">^</a> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation journal cs1"><a rel="nofollow" class="external text" href="https://lemesurierb.people.charleston.edu/elementary-numerical-analysis-python/notebooks/machine-numbers-rounding-error-and-error-propagation-python.html">"9. Machine Numbers, Rounding Error and Error Propagation"</a>. <a href="/wiki/College_of_Charleston" title="College of Charleston">College of Charleston</a>. 8 February 2021.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=College+of+Charleston&rft.atitle=9.+Machine+Numbers%2C+Rounding+Error+and+Error+Propagation&rft.date=2021-02-08&rft_id=https%3A%2F%2Flemesurierb.people.charleston.edu%2Felementary-numerical-analysis-python%2Fnotebooks%2Fmachine-numbers-rounding-error-and-error-propagation-python.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2>[<a href="/w/index.php?title=Division_algorithm&action=edit&section=21" title="Edit section: Further reading">edit</a>]</div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSavard2018" class="citation web cs1">Savard, John J. G. (2018) [2006]. <a rel="nofollow" class="external text" href="http://www.quadibloc.com/comp/cp0202.htm">"Advanced Arithmetic Techniques"</a>. quadibloc. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20180703001722/http://www.quadibloc.com/comp/cp0202.htm">Archived</a> from the original on 2018-07-03. Retrieved 2018-07-16.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=quadibloc&rft.atitle=Advanced+Arithmetic+Techniques&rft.date=2018&rft.aulast=Savard&rft.aufirst=John+J.+G.&rft_id=http%3A%2F%2Fwww.quadibloc.com%2Fcomp%2Fcp0202.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADivision+algorithm" class="Z3988"></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Number-theoretic_algorithms" style="padding:3px"><table class="nowraplinks mw-collapsible uncollapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Number-theoretic_algorithms" title="Template:Number-theoretic algorithms"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Number-theoretic_algorithms" title="Template talk:Number-theoretic algorithms"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Number-theoretic_algorithms" title="Special:EditPage/Template:Number-theoretic algorithms"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Number-theoretic_algorithms" style="font-size:114%;margin:0 4em"><a href="/wiki/Number_theory" title="Number theory">Number-theoretic</a> <a href="/wiki/Algorithm" title="Algorithm">algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Primality_test" title="Primality test">Primality tests</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/AKS_primality_test" title="AKS primality test">AKS</a></li> <li><a href="/wiki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test" title="Adleman–Pomerance–Rumely primality test">APR</a></li> <li><a href="/wiki/Baillie%E2%80%93PSW_primality_test" title="Baillie–PSW primality test">Baillie–PSW</a></li> <li><a href="/wiki/Elliptic_curve_primality" title="Elliptic curve primality">Elliptic curve</a></li> <li><a href="/wiki/Pocklington_primality_test" title="Pocklington primality test">Pocklington</a></li> <li><a href="/wiki/Fermat_primality_test" title="Fermat primality test">Fermat</a></li> <li><a href="/wiki/Lucas_primality_test" title="Lucas primality test">Lucas</a></li> <li><a href="/wiki/Lucas%E2%80%93Lehmer_primality_test" title="Lucas–Lehmer primality test">Lucas–Lehmer</a></li> <li><a href="/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test" title="Lucas–Lehmer–Riesel test">Lucas–Lehmer–Riesel</a></li> <li><a href="/wiki/Proth%27s_theorem" title="Proth's theorem">Proth's theorem</a></li> <li><a href="/wiki/P%C3%A9pin%27s_test" title="Pépin's test">Pépin's</a></li> <li><a href="/wiki/Quadratic_Frobenius_test" title="Quadratic Frobenius test">Quadratic Frobenius</a></li> <li><a href="/wiki/Solovay%E2%80%93Strassen_primality_test" title="Solovay–Strassen primality test">Solovay–Strassen</a></li> <li><a href="/wiki/Miller%E2%80%93Rabin_primality_test" title="Miller–Rabin primality test">Miller–Rabin</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Generating_primes" class="mw-redirect" title="Generating primes">Prime-generating</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Sieve_of_Atkin" title="Sieve of Atkin">Sieve of Atkin</a></li> <li><a href="/wiki/Sieve_of_Eratosthenes" title="Sieve of Eratosthenes">Sieve of Eratosthenes</a></li> <li><a href="/wiki/Sieve_of_Pritchard" title="Sieve of Pritchard">Sieve of Pritchard</a></li> <li><a href="/wiki/Sieve_of_Sundaram" title="Sieve of Sundaram">Sieve of Sundaram</a></li> <li><a href="/wiki/Wheel_factorization" title="Wheel factorization">Wheel factorization</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Integer_factorization" title="Integer factorization">Integer factorization</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Continued_fraction_factorization" title="Continued fraction factorization">Continued fraction (CFRAC)</a></li> <li><a href="/wiki/Dixon%27s_factorization_method" title="Dixon's factorization method">Dixon's</a></li> <li><a href="/wiki/Lenstra_elliptic-curve_factorization" title="Lenstra elliptic-curve factorization">Lenstra elliptic curve (ECM)</a></li> <li><a href="/wiki/Euler%27s_factorization_method" title="Euler's factorization method">Euler's</a></li> <li><a href="/wiki/Pollard%27s_rho_algorithm" title="Pollard's rho algorithm">Pollard's rho</a></li> <li><a href="/wiki/Pollard%27s_p_%E2%88%92_1_algorithm" title="Pollard's p − 1 algorithm">p − 1</a></li> <li><a href="/wiki/Williams%27s_p_%2B_1_algorithm" title="Williams's p + 1 algorithm">p + 1</a></li> <li><a href="/wiki/Quadratic_sieve" title="Quadratic sieve">Quadratic sieve (QS)</a></li> <li><a href="/wiki/General_number_field_sieve" title="General number field sieve">General number field sieve (GNFS)</a></li> <li><a href="/wiki/Special_number_field_sieve" title="Special number field sieve">Special number field sieve (SNFS)</a></li> <li><a href="/wiki/Rational_sieve" title="Rational sieve">Rational sieve</a></li> <li><a href="/wiki/Fermat%27s_factorization_method" title="Fermat's factorization method">Fermat's</a></li> <li><a href="/wiki/Shanks%27s_square_forms_factorization" title="Shanks's square forms factorization">Shanks's square forms</a></li> <li><a href="/wiki/Trial_division" title="Trial division">Trial division</a></li> <li><a href="/wiki/Shor%27s_algorithm" title="Shor's algorithm">Shor's</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Multiplication_algorithm" title="Multiplication algorithm">Multiplication</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Ancient_Egyptian_multiplication" title="Ancient Egyptian multiplication">Ancient Egyptian</a></li> <li><a href="/wiki/Long_multiplication" class="mw-redirect" title="Long multiplication">Long</a></li> <li><a href="/wiki/Karatsuba_algorithm" title="Karatsuba algorithm">Karatsuba</a></li> <li><a href="/wiki/Toom%E2%80%93Cook_multiplication" title="Toom–Cook multiplication">Toom–Cook</a></li> <li><a href="/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm" title="Schönhage–Strassen algorithm">Schönhage–Strassen</a></li> <li><a href="/wiki/F%C3%BCrer%27s_algorithm" class="mw-redirect" title="Fürer's algorithm">Fürer's</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Euclidean_division" title="Euclidean division">Euclidean</a> <a class="mw-selflink selflink">division</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_division" class="mw-redirect" title="Binary division">Binary</a></li> <li><a href="/wiki/Chunking_(division)" title="Chunking (division)">Chunking</a></li> <li><a href="/wiki/Fourier_division" title="Fourier division">Fourier</a></li> <li><a href="/wiki/Goldschmidt_division" class="mw-redirect" title="Goldschmidt division">Goldschmidt</a></li> <li><a href="/wiki/Newton%E2%80%93Raphson_division" class="mw-redirect" title="Newton–Raphson division">Newton-Raphson</a></li> <li><a href="/wiki/Long_division" title="Long division">Long</a></li> <li><a href="/wiki/Short_division" title="Short division">Short</a></li> <li><a href="/wiki/SRT_division" class="mw-redirect" title="SRT division">SRT</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Discrete_logarithm" title="Discrete logarithm">Discrete logarithm</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Baby-step_giant-step" title="Baby-step giant-step">Baby-step giant-step</a></li> <li><a href="/wiki/Pollard%27s_rho_algorithm_for_logarithms" title="Pollard's rho algorithm for logarithms">Pollard rho</a></li> <li><a href="/wiki/Pollard%27s_kangaroo_algorithm" title="Pollard's kangaroo algorithm">Pollard kangaroo</a></li> <li><a href="/wiki/Pohlig%E2%80%93Hellman_algorithm" title="Pohlig–Hellman algorithm">Pohlig–Hellman</a></li> <li><a href="/wiki/Index_calculus_algorithm" title="Index calculus algorithm">Index calculus</a></li> <li><a href="/wiki/Function_field_sieve" title="Function field sieve">Function field sieve</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Greatest_common_divisor" title="Greatest common divisor">Greatest common divisor</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_GCD_algorithm" title="Binary GCD algorithm">Binary</a></li> <li><a href="/wiki/Euclidean_algorithm" title="Euclidean algorithm">Euclidean</a></li> <li><a href="/wiki/Extended_Euclidean_algorithm" title="Extended Euclidean algorithm">Extended Euclidean</a></li> <li><a href="/wiki/Lehmer%27s_GCD_algorithm" title="Lehmer's GCD algorithm">Lehmer's</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Quadratic_residue" title="Quadratic residue">Modular square root</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Cipolla%27s_algorithm" title="Cipolla's algorithm">Cipolla</a></li> <li><a href="/wiki/Pocklington%27s_algorithm" title="Pocklington's algorithm">Pocklington's</a></li> <li><a href="/wiki/Tonelli%E2%80%93Shanks_algorithm" title="Tonelli–Shanks algorithm">Tonelli–Shanks</a></li> <li><a href="/wiki/Berlekamp%E2%80%93Rabin_algorithm" title="Berlekamp–Rabin algorithm">Berlekamp</a></li> <li><a href="/wiki/Kunerth%27s_algorithm" title="Kunerth's algorithm">Kunerth</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other algorithms</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Chakravala_method" title="Chakravala method">Chakravala</a></li> <li><a href="/wiki/Cornacchia%27s_algorithm" title="Cornacchia's algorithm">Cornacchia</a></li> <li><a href="/wiki/Exponentiation_by_squaring" title="Exponentiation by squaring">Exponentiation by squaring</a></li> <li><a href="/wiki/Integer_square_root" title="Integer square root">Integer square root</a></li> <li><a href="/wiki/Integer_relation_algorithm" title="Integer relation algorithm">Integer relation</a> (<a href="/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm" title="Lenstra–Lenstra–Lovász lattice basis reduction algorithm">LLL</a>; <a href="/wiki/Korkine%E2%80%93Zolotarev_lattice_basis_reduction_algorithm" title="Korkine–Zolotarev lattice basis reduction algorithm">KZ</a>)</li> <li><a href="/wiki/Modular_exponentiation" title="Modular exponentiation">Modular exponentiation</a></li> <li><a href="/wiki/Montgomery_reduction" class="mw-redirect" title="Montgomery reduction">Montgomery reduction</a></li> <li><a href="/wiki/Schoof%27s_algorithm" title="Schoof's algorithm">Schoof</a></li> <li><a href="/wiki/Trachtenberg_system" title="Trachtenberg system">Trachtenberg system</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow hlist" colspan="2"><div> <ul><li>Italics indicate that algorithm is for numbers of special forms</li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Division_algorithm&oldid=1246386441#Goldschmidt_division">https://en.wikipedia.org/w/index.php?title=Division_algorithm&oldid=1246386441#Goldschmidt_division</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Binary_arithmetic" title="Category:Binary arithmetic">Binary arithmetic</a></li><li><a href="/wiki/Category:Computer_arithmetic" title="Category:Computer arithmetic">Computer arithmetic</a></li><li><a href="/wiki/Category:Division_(mathematics)" title="Category:Division (mathematics)">Division (mathematics)</a></li><li><a href="/wiki/Category:Computer_arithmetic_algorithms" title="Category:Computer arithmetic algorithms">Computer arithmetic algorithms</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:CS1_maint:_location_missing_publisher" title="Category:CS1 maint: location missing publisher">CS1 maint: location missing publisher</a></li><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_February_2012" title="Category:Articles with unsourced statements from February 2012">Articles with unsourced statements from February 2012</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_February_2014" title="Category:Articles with unsourced statements from February 2014">Articles with unsourced statements from February 2014</a></li><li><a href="/wiki/Category:All_pages_needing_factual_verification" title="Category:All pages needing factual verification">All pages needing factual verification</a></li><li><a href="/wiki/Category:Wikipedia_articles_needing_factual_verification_from_June_2015" title="Category:Wikipedia articles needing factual verification from June 2015">Wikipedia articles needing factual verification from June 2015</a></li><li><a href="/wiki/Category:Articles_to_be_expanded_from_September_2012" title="Category:Articles to be expanded from September 2012">Articles to be expanded from September 2012</a></li><li><a href="/wiki/Category:All_articles_to_be_expanded" title="Category:All articles to be expanded">All articles to be expanded</a></li><li><a href="/wiki/Category:Articles_with_example_pseudocode" title="Category:Articles with example pseudocode">Articles with example pseudocode</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 18 September 2024, at 16:52 (UTC).</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Division_algorithm&mobileaction=toggle_view_mobile#Goldschmidt_division" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-r5q8s","wgBackendResponseTime":150,"wgPageParseReport":{"limitreport":{"cputime":"0.941","walltime":"1.654","ppvisitednodes":{"value":3667,"limit":1000000},"postexpandincludesize":{"value":95777,"limit":2097152},"templateargumentsize":{"value":3724,"limit":2097152},"expansiondepth":{"value":16,"limit":100},"expensivefunctioncount":{"value":16,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":133150,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 1325.638 1 -total"," 25.13% 333.132 2 Template:Reflist"," 9.08% 120.367 1 Template:Short_description"," 8.51% 112.757 3 Template:Cite_tech_report"," 7.83% 103.765 1 Template:Number-theoretic_algorithms"," 7.57% 100.397 1 Template:Navbox"," 5.84% 77.476 12 Template:Cite_journal"," 5.73% 76.001 2 Template:Pagetype"," 5.01% 66.354 3 Template:Fix"," 4.37% 57.915 2 Template:Citation_needed"]},"scribunto":{"limitreport-timeusage":{"value":"0.516","limit":"10.000"},"limitreport-memusage":{"value":9436267,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-dhbcv","timestamp":"20241122142204","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Division algorithm","url":"https:\/\/en.wikipedia.org\/wiki\/Division_algorithm#Goldschmidt_division","sameAs":"http:\/\/www.wikidata.org\/entity\/Q3526714","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q3526714","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2005-12-06T06:57:21Z","dateModified":"2024-09-18T16:52:06Z","headline":"algorithm for quotient and remainder of integer division"}</script> </body> </html>

CINXE.COM

Division algorithm - Wikipedia