Number of computations for multiplication
$begingroup$
I just read Marvin Minskys' "Form and Content in Computer Science" and found myself confused with the following paragraph:
A startling discovery was made about multiplication itself in the
thesis of S.A. Cook [3], which uses a result of A.L. Toom, as
discussed in Knuth [4]. Consider the ordinary algorithm for
multiplying decimal numbers: for two n-digit numbers this employs
n-squared one-digit products. It is usually supposed that this is
minimal. But suppose we write the numbers in two halves, so that the
product is N = (#A+B)(#C+D), where # stands for multiplying by 10 subscript{n/2}.
(The left-shift operation is considered to have negligible cost.) Then
one can verify that
N = ##AC + BD + #(A+B)(C+D) - #(AC+BD).
This involves only three half-length multiplications, instead of the
four that one might suppose were needed. For large n, the reduction
can obviously be reapplied over and over to the smaller numbers. The
price is a growing number of additions. By compounding this and other
ideas, Cook showed that for any e and large enough n, multiplication
requires less than n*(1-e) products, instead of the expected
n-squared.
I got stuck when I read stands for multiplying by 10 ... because I didn't understand what the subscript in this example means. I tried to find it out by googling about the complexity of multiplication and stuff like that, but couldn't find the answer.
Can you point me in the right direction here? I guess that this exact part is essential for understanding the formula in the middle. I would like to find out how this computation would resolve a multiplication.
complexity-theory multiplication
asked 16 hours ago
Fabian SchneiderFabian Schneider
183
New contributor
Fabian Schneider is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I just read Marvin Minskys' "Form and Content in Computer Science" and found myself confused with the following paragraph:
A startling discovery was made about multiplication itself in the
thesis of S.A. Cook [3], which uses a result of A.L. Toom, as
discussed in Knuth [4]. Consider the ordinary algorithm for
multiplying decimal numbers: for two n-digit numbers this employs
n-squared one-digit products. It is usually supposed that this is
minimal. But suppose we write the numbers in two halves, so that the
product is N = (#A+B)(#C+D), where # stands for multiplying by 10 subscript{n/2}.
(The left-shift operation is considered to have negligible cost.) Then
one can verify that
N = ##AC + BD + #(A+B)(C+D) - #(AC+BD).
This involves only three half-length multiplications, instead of the
four that one might suppose were needed. For large n, the reduction
can obviously be reapplied over and over to the smaller numbers. The
price is a growing number of additions. By compounding this and other
ideas, Cook showed that for any e and large enough n, multiplication
requires less than n*(1-e) products, instead of the expected
n-squared.
I got stuck when I read stands for multiplying by 10 ... because I didn't understand what the subscript in this example means. I tried to find it out by googling about the complexity of multiplication and stuff like that, but couldn't find the answer.
Can you point me in the right direction here? I guess that this exact part is essential for understanding the formula in the middle. I would like to find out how this computation would resolve a multiplication.
complexity-theory multiplication
asked 16 hours ago
Fabian SchneiderFabian Schneider
183
New contributor
Fabian Schneider is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I just read Marvin Minskys' "Form and Content in Computer Science" and found myself confused with the following paragraph:
A startling discovery was made about multiplication itself in the
thesis of S.A. Cook [3], which uses a result of A.L. Toom, as
discussed in Knuth [4]. Consider the ordinary algorithm for
multiplying decimal numbers: for two n-digit numbers this employs
n-squared one-digit products. It is usually supposed that this is
minimal. But suppose we write the numbers in two halves, so that the
product is N = (#A+B)(#C+D), where # stands for multiplying by 10 subscript{n/2}.
(The left-shift operation is considered to have negligible cost.) Then
one can verify that
N = ##AC + BD + #(A+B)(C+D) - #(AC+BD).
This involves only three half-length multiplications, instead of the
four that one might suppose were needed. For large n, the reduction
can obviously be reapplied over and over to the smaller numbers. The
price is a growing number of additions. By compounding this and other
ideas, Cook showed that for any e and large enough n, multiplication
requires less than n*(1-e) products, instead of the expected
n-squared.
I got stuck when I read stands for multiplying by 10 ... because I didn't understand what the subscript in this example means. I tried to find it out by googling about the complexity of multiplication and stuff like that, but couldn't find the answer.
Can you point me in the right direction here? I guess that this exact part is essential for understanding the formula in the middle. I would like to find out how this computation would resolve a multiplication.
complexity-theory multiplication
asked 16 hours ago
Fabian SchneiderFabian Schneider
183
New contributor
Fabian Schneider is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I just read Marvin Minskys' "Form and Content in Computer Science" and found myself confused with the following paragraph:
A startling discovery was made about multiplication itself in the
thesis of S.A. Cook [3], which uses a result of A.L. Toom, as
discussed in Knuth [4]. Consider the ordinary algorithm for
multiplying decimal numbers: for two n-digit numbers this employs
n-squared one-digit products. It is usually supposed that this is
minimal. But suppose we write the numbers in two halves, so that the
product is N = (#A+B)(#C+D), where # stands for multiplying by 10 subscript{n/2}.
(The left-shift operation is considered to have negligible cost.) Then
one can verify that
N = ##AC + BD + #(A+B)(C+D) - #(AC+BD).
This involves only three half-length multiplications, instead of the
four that one might suppose were needed. For large n, the reduction
can obviously be reapplied over and over to the smaller numbers. The
price is a growing number of additions. By compounding this and other
ideas, Cook showed that for any e and large enough n, multiplication
requires less than n*(1-e) products, instead of the expected
n-squared.
I got stuck when I read stands for multiplying by 10 ... because I didn't understand what the subscript in this example means. I tried to find it out by googling about the complexity of multiplication and stuff like that, but couldn't find the answer.
Can you point me in the right direction here? I guess that this exact part is essential for understanding the formula in the middle. I would like to find out how this computation would resolve a multiplication.
complexity-theory multiplication
complexity-theory multiplication
asked 16 hours ago
Fabian SchneiderFabian Schneider
183
New contributor
Fabian Schneider is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 16 hours ago
Fabian SchneiderFabian Schneider
183
New contributor
Fabian Schneider is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 16 hours ago
Fabian SchneiderFabian Schneider
183
New contributor
Fabian Schneider is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 16 hours ago
Fabian SchneiderFabian Schneider
183
asked 16 hours ago
Fabian SchneiderFabian Schneider
183
183
New contributor
Fabian Schneider is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Fabian Schneider is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Fabian Schneider 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 |
2 Answers
2
active
oldest
votes
$begingroup$
It should be "10 superscript{n/2}" meaning $10^{n/2}$. For example, if $n=4$, then "6#2" would represent $6cdot10^2=600$. All he's doing is shifting a decimal number to the left.
answered 15 hours ago
Rick DeckerRick Decker
12.7k33044
$endgroup$
add a comment |
$begingroup$
From context it's just exponentiation. I don't know why it's written with a subscript instead of a superscript, but with older papers you sometimes had a professional typesetter who might not have understood the material. (Of course nowadays typically do their own typesetting.)
answered 15 hours ago
Daniel McLauryDaniel McLaury
48427
$endgroup$
add a comment |
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: "419"
};
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
});
}
});
Fabian Schneider 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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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%2fcs.stackexchange.com%2fquestions%2f104548%2fnumber-of-computations-for-multiplication%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It should be "10 superscript{n/2}" meaning $10^{n/2}$. For example, if $n=4$, then "6#2" would represent $6cdot10^2=600$. All he's doing is shifting a decimal number to the left.
answered 15 hours ago
Rick DeckerRick Decker
12.7k33044
$endgroup$
add a comment |
$begingroup$
It should be "10 superscript{n/2}" meaning $10^{n/2}$. For example, if $n=4$, then "6#2" would represent $6cdot10^2=600$. All he's doing is shifting a decimal number to the left.
answered 15 hours ago
Rick DeckerRick Decker
12.7k33044
$endgroup$
add a comment |
$begingroup$
It should be "10 superscript{n/2}" meaning $10^{n/2}$. For example, if $n=4$, then "6#2" would represent $6cdot10^2=600$. All he's doing is shifting a decimal number to the left.
answered 15 hours ago
Rick DeckerRick Decker
12.7k33044
$endgroup$
It should be "10 superscript{n/2}" meaning $10^{n/2}$. For example, if $n=4$, then "6#2" would represent $6cdot10^2=600$. All he's doing is shifting a decimal number to the left.
answered 15 hours ago
Rick DeckerRick Decker
12.7k33044
answered 15 hours ago
Rick DeckerRick Decker
12.7k33044
answered 15 hours ago
Rick DeckerRick Decker
12.7k33044
answered 15 hours ago
Rick DeckerRick Decker
12.7k33044
12.7k33044
add a comment |
add a comment |
$begingroup$
From context it's just exponentiation. I don't know why it's written with a subscript instead of a superscript, but with older papers you sometimes had a professional typesetter who might not have understood the material. (Of course nowadays typically do their own typesetting.)
answered 15 hours ago
Daniel McLauryDaniel McLaury
48427
$endgroup$
add a comment |
$begingroup$
From context it's just exponentiation. I don't know why it's written with a subscript instead of a superscript, but with older papers you sometimes had a professional typesetter who might not have understood the material. (Of course nowadays typically do their own typesetting.)
answered 15 hours ago
Daniel McLauryDaniel McLaury
48427
$endgroup$
add a comment |
$begingroup$
From context it's just exponentiation. I don't know why it's written with a subscript instead of a superscript, but with older papers you sometimes had a professional typesetter who might not have understood the material. (Of course nowadays typically do their own typesetting.)
answered 15 hours ago
Daniel McLauryDaniel McLaury
48427
$endgroup$
From context it's just exponentiation. I don't know why it's written with a subscript instead of a superscript, but with older papers you sometimes had a professional typesetter who might not have understood the material. (Of course nowadays typically do their own typesetting.)
answered 15 hours ago
Daniel McLauryDaniel McLaury
48427
answered 15 hours ago
Daniel McLauryDaniel McLaury
48427
answered 15 hours ago
Daniel McLauryDaniel McLaury
48427
answered 15 hours ago
Daniel McLauryDaniel McLaury
48427
48427
add a comment |
add a comment |
Fabian Schneider is a new contributor. Be nice, and check out our Code of Conduct.
Fabian Schneider is a new contributor. Be nice, and check out our Code of Conduct.
Fabian Schneider is a new contributor. Be nice, and check out our Code of Conduct.
Fabian Schneider is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science 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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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%2fcs.stackexchange.com%2fquestions%2f104548%2fnumber-of-computations-for-multiplication%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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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
