Mixing
Complexity of the Newton's method approximation of $frac{R}{b}$
$begingroup$
I am trying to understand a particular concept in this lecture.
The lecture goes on to describe that to compute a division of $frac{a}{b}$, you have to:
Compute high-precision representation of $frac{1}{b}$ first (that is the floor of $frac{R}{b}$ where $R$ is a large value that is easy to divide by).
Multiply the high-precision representation of $frac{1}{b}$ by $a$ then divide by $R$? (The lecture doesn't state this part).
In the process of using Newton's method to estimate $frac{R}{b}$ (see page 3), the lecture states (in the beginning of page 4) that 'division requires multiplication of different-sized numbers at each iteration'. This leads to the a complexity of $theta(d^alpha)$ for some $alpha geq 1$, as argued in page 4.
How's that the case? In the example given on page 3, division requires multiplication of d-sized numbers on each iteration leading to a complexity of $theta(log{d} * d^alpha)$. So, how exactly is the statement above, in bold, true?
discrete-mathematics algorithms computational-complexity newton-raphson
asked Jan 6 at 5:04
user617040user617040
35
$endgroup$
add a comment |
$begingroup$
I am trying to understand a particular concept in this lecture.
The lecture goes on to describe that to compute a division of $frac{a}{b}$, you have to:
Compute high-precision representation of $frac{1}{b}$ first (that is the floor of $frac{R}{b}$ where $R$ is a large value that is easy to divide by).
Multiply the high-precision representation of $frac{1}{b}$ by $a$ then divide by $R$? (The lecture doesn't state this part).
In the process of using Newton's method to estimate $frac{R}{b}$ (see page 3), the lecture states (in the beginning of page 4) that 'division requires multiplication of different-sized numbers at each iteration'. This leads to the a complexity of $theta(d^alpha)$ for some $alpha geq 1$, as argued in page 4.
How's that the case? In the example given on page 3, division requires multiplication of d-sized numbers on each iteration leading to a complexity of $theta(log{d} * d^alpha)$. So, how exactly is the statement above, in bold, true?
discrete-mathematics algorithms computational-complexity newton-raphson
asked Jan 6 at 5:04
user617040user617040
35
$endgroup$
add a comment |
$begingroup$
I am trying to understand a particular concept in this lecture.
The lecture goes on to describe that to compute a division of $frac{a}{b}$, you have to:
Compute high-precision representation of $frac{1}{b}$ first (that is the floor of $frac{R}{b}$ where $R$ is a large value that is easy to divide by).
Multiply the high-precision representation of $frac{1}{b}$ by $a$ then divide by $R$? (The lecture doesn't state this part).
In the process of using Newton's method to estimate $frac{R}{b}$ (see page 3), the lecture states (in the beginning of page 4) that 'division requires multiplication of different-sized numbers at each iteration'. This leads to the a complexity of $theta(d^alpha)$ for some $alpha geq 1$, as argued in page 4.
How's that the case? In the example given on page 3, division requires multiplication of d-sized numbers on each iteration leading to a complexity of $theta(log{d} * d^alpha)$. So, how exactly is the statement above, in bold, true?
discrete-mathematics algorithms computational-complexity newton-raphson
asked Jan 6 at 5:04
user617040user617040
35
$endgroup$
I am trying to understand a particular concept in this lecture.
The lecture goes on to describe that to compute a division of $frac{a}{b}$, you have to:
Compute high-precision representation of $frac{1}{b}$ first (that is the floor of $frac{R}{b}$ where $R$ is a large value that is easy to divide by).
Multiply the high-precision representation of $frac{1}{b}$ by $a$ then divide by $R$? (The lecture doesn't state this part).
In the process of using Newton's method to estimate $frac{R}{b}$ (see page 3), the lecture states (in the beginning of page 4) that 'division requires multiplication of different-sized numbers at each iteration'. This leads to the a complexity of $theta(d^alpha)$ for some $alpha geq 1$, as argued in page 4.
How's that the case? In the example given on page 3, division requires multiplication of d-sized numbers on each iteration leading to a complexity of $theta(log{d} * d^alpha)$. So, how exactly is the statement above, in bold, true?
discrete-mathematics algorithms computational-complexity newton-raphson
discrete-mathematics algorithms computational-complexity newton-raphson
asked Jan 6 at 5:04
user617040user617040
35
asked Jan 6 at 5:04
user617040user617040
35
edited Jan 7 at 0:34
user617040
asked Jan 6 at 5:04
user617040user617040
35
asked Jan 6 at 5:04
user617040user617040
35
asked Jan 6 at 5:04
user617040user617040
35
35
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3063512%2fcomplexity-of-the-newtons-method-approximation-of-fracrb%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3063512%2fcomplexity-of-the-newtons-method-approximation-of-fracrb%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
