SICP - exercise 1.45 - are these solutions equivalent?
QUESTION:
I'm going through the exercise in SICP and am wondering if someone can explain the difference between these 2 seemingly equivalent functions that are giving different results! Is this because of rounding?? I'm thinking the order of functions shouldn't matter here but somehow it does? Can someone explain what's going on here and why it's different?
Details:
Exercise 1.45: ..saw that finding a fixed point of y => x/y does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped y => x/y^2. Unfortunately,
the process does not work for fourth roots—a single average damp is not enough to make a fixed-point search for y => x/y^3 converge. On the other hand, if we
average damp twice (i.e., use the average damp of the average damp of y => x/y^3) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute nth roots as a fixedpoint search based upon repeated average damping of y =>x/y^(n-1). Use this to implement a simple procedure for computing the roots using fixed-point, average-damp, and the
repeated procedure of Exercise 1.43. Assume that any arithmetic operations you need are available as primitives.
My answer (note order of repeat and average-damping):
(define (nth-root-me x n num-repetitions)
(fixed-point (repeat (average-damping (lambda (y) (/ x (expt y (- n 1)))))
num-repetitions)
1.0))
I see an alternate web solution where repeat is called direcly on average damp and then that function is called with the argument
(define (nth-root-web-solution x n num-repetitions)
(fixed-point
((repeat average-damping num-repetition)
(lambda (y) (/ x (expt y (- n 1)))))
1.0))
Now calling both of these, there seems to be a difference in the answers and I can't understand why! My understanding is the order of the functions shouldn't affect the output (they're associative right?), but clearly it is!
(nth-root-me 10000 4 2)
10.050110705350287
(nth-root-web-solution 10000 4 2)
10.0
I did more tests and it's always like this, my answer is close, but the other answer is almost always closer!
Can someone explain what's going on? Why aren't these equivalent?
functional-programming lisp scheme sicp
asked 2 mins ago
ajivani
101
New contributor
ajivani is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
QUESTION:
I'm going through the exercise in SICP and am wondering if someone can explain the difference between these 2 seemingly equivalent functions that are giving different results! Is this because of rounding?? I'm thinking the order of functions shouldn't matter here but somehow it does? Can someone explain what's going on here and why it's different?
Details:
Exercise 1.45: ..saw that finding a fixed point of y => x/y does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped y => x/y^2. Unfortunately,
the process does not work for fourth roots—a single average damp is not enough to make a fixed-point search for y => x/y^3 converge. On the other hand, if we
average damp twice (i.e., use the average damp of the average damp of y => x/y^3) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute nth roots as a fixedpoint search based upon repeated average damping of y =>x/y^(n-1). Use this to implement a simple procedure for computing the roots using fixed-point, average-damp, and the
repeated procedure of Exercise 1.43. Assume that any arithmetic operations you need are available as primitives.
My answer (note order of repeat and average-damping):
(define (nth-root-me x n num-repetitions)
(fixed-point (repeat (average-damping (lambda (y) (/ x (expt y (- n 1)))))
num-repetitions)
1.0))
I see an alternate web solution where repeat is called direcly on average damp and then that function is called with the argument
(define (nth-root-web-solution x n num-repetitions)
(fixed-point
((repeat average-damping num-repetition)
(lambda (y) (/ x (expt y (- n 1)))))
1.0))
Now calling both of these, there seems to be a difference in the answers and I can't understand why! My understanding is the order of the functions shouldn't affect the output (they're associative right?), but clearly it is!
(nth-root-me 10000 4 2)
10.050110705350287
(nth-root-web-solution 10000 4 2)
10.0
I did more tests and it's always like this, my answer is close, but the other answer is almost always closer!
Can someone explain what's going on? Why aren't these equivalent?
functional-programming lisp scheme sicp
asked 2 mins ago
ajivani
101
New contributor
ajivani is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
QUESTION:
I'm going through the exercise in SICP and am wondering if someone can explain the difference between these 2 seemingly equivalent functions that are giving different results! Is this because of rounding?? I'm thinking the order of functions shouldn't matter here but somehow it does? Can someone explain what's going on here and why it's different?
Details:
Exercise 1.45: ..saw that finding a fixed point of y => x/y does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped y => x/y^2. Unfortunately,
the process does not work for fourth roots—a single average damp is not enough to make a fixed-point search for y => x/y^3 converge. On the other hand, if we
average damp twice (i.e., use the average damp of the average damp of y => x/y^3) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute nth roots as a fixedpoint search based upon repeated average damping of y =>x/y^(n-1). Use this to implement a simple procedure for computing the roots using fixed-point, average-damp, and the
repeated procedure of Exercise 1.43. Assume that any arithmetic operations you need are available as primitives.
My answer (note order of repeat and average-damping):
(define (nth-root-me x n num-repetitions)
(fixed-point (repeat (average-damping (lambda (y) (/ x (expt y (- n 1)))))
num-repetitions)
1.0))
I see an alternate web solution where repeat is called direcly on average damp and then that function is called with the argument
(define (nth-root-web-solution x n num-repetitions)
(fixed-point
((repeat average-damping num-repetition)
(lambda (y) (/ x (expt y (- n 1)))))
1.0))
Now calling both of these, there seems to be a difference in the answers and I can't understand why! My understanding is the order of the functions shouldn't affect the output (they're associative right?), but clearly it is!
(nth-root-me 10000 4 2)
10.050110705350287
(nth-root-web-solution 10000 4 2)
10.0
I did more tests and it's always like this, my answer is close, but the other answer is almost always closer!
Can someone explain what's going on? Why aren't these equivalent?
functional-programming lisp scheme sicp
asked 2 mins ago
ajivani
101
New contributor
ajivani is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
QUESTION:
I'm going through the exercise in SICP and am wondering if someone can explain the difference between these 2 seemingly equivalent functions that are giving different results! Is this because of rounding?? I'm thinking the order of functions shouldn't matter here but somehow it does? Can someone explain what's going on here and why it's different?
Details:
Exercise 1.45: ..saw that finding a fixed point of y => x/y does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped y => x/y^2. Unfortunately,
the process does not work for fourth roots—a single average damp is not enough to make a fixed-point search for y => x/y^3 converge. On the other hand, if we
average damp twice (i.e., use the average damp of the average damp of y => x/y^3) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute nth roots as a fixedpoint search based upon repeated average damping of y =>x/y^(n-1). Use this to implement a simple procedure for computing the roots using fixed-point, average-damp, and the
repeated procedure of Exercise 1.43. Assume that any arithmetic operations you need are available as primitives.
My answer (note order of repeat and average-damping):
(define (nth-root-me x n num-repetitions)
(fixed-point (repeat (average-damping (lambda (y) (/ x (expt y (- n 1)))))
num-repetitions)
1.0))
I see an alternate web solution where repeat is called direcly on average damp and then that function is called with the argument
(define (nth-root-web-solution x n num-repetitions)
(fixed-point
((repeat average-damping num-repetition)
(lambda (y) (/ x (expt y (- n 1)))))
1.0))
Now calling both of these, there seems to be a difference in the answers and I can't understand why! My understanding is the order of the functions shouldn't affect the output (they're associative right?), but clearly it is!
(nth-root-me 10000 4 2)
10.050110705350287
(nth-root-web-solution 10000 4 2)
10.0
I did more tests and it's always like this, my answer is close, but the other answer is almost always closer!
Can someone explain what's going on? Why aren't these equivalent?
functional-programming lisp scheme sicp
functional-programming lisp scheme sicp
asked 2 mins ago
ajivani
101
New contributor
ajivani is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 mins ago
ajivani
101
New contributor
ajivani is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 mins ago
ajivani
101
New contributor
ajivani is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 mins ago
ajivani
101
asked 2 mins ago
ajivani
101
101
New contributor
ajivani is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
ajivani is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
ajivani is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
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.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
ajivani is a new contributor. Be nice, and check out our Code of Conduct.
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%2fcodereview.stackexchange.com%2fquestions%2f210302%2fsicp-exercise-1-45-are-these-solutions-equivalent%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
ajivani is a new contributor. Be nice, and check out our Code of Conduct.
ajivani is a new contributor. Be nice, and check out our Code of Conduct.
ajivani is a new contributor. Be nice, and check out our Code of Conduct.
ajivani is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2fcodereview.stackexchange.com%2fquestions%2f210302%2fsicp-exercise-1-45-are-these-solutions-equivalent%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
