How can I iterate this process?Possible Memory Leak Issues in NestWhileConditional Gathering of listsHow to find first list element that differs from average of N previous elements by more than a given amount?How to simplify a resistence network and represent the simplifying process?Taking derivative using some variableSort matrix rows and columns while keeping headingCombining Lists in a specified sequenceNeed to add a different random number to each part of the tableBuilding a list of products from the elements in another listEfficient way to iterate over large list and check conditions
Does a code snippet compile? Or does it get compiled?
Max Order of an Isogeny Class of Rational Elliptic Curves is 8?
How can I iterate this process?
(11 of 11: Meta) What is Pyramid Cult's All-Time Favorite?
Why couldn't soldiers sight their own weapons without officers' orders?
Is refreshing multiple times a test case for web applications?
How can you evade tax by getting employment income just in equity, then using this equity as collateral to take out loan?
Why are Gatwick's runways too close together?
As a 16 year old, how can I keep my money safe from my mother?
Can I call myself an assistant professor without a PhD?
What's this thing in a peltier cooler?
How do I explain to a team that the project they will work on for six months will certainly be cancelled?
Plausibility of Ice Eaters in the Arctic
Non-OR journals which regularly publish OR research
Shabbat clothing on shabbat chazon
Was the 2019 Lion King film made through motion capture?
Is it really ~648.69 km/s delta-v to "land" on the surface of the Sun?
Visa National - No Exit Stamp From France on Return to the UK
How would I as a DM create a smart phone-like spell/device my players could use?
Generator for parity?
Could one become a successful researcher by writing some really good papers while being outside academia?
Optimal way to extract "positive part" of a multivariate polynomial
In Pokémon Go, why does one of my Pikachu have an option to evolve, but another one doesn't?
How does The Fools Guild make its money?
How can I iterate this process?
Possible Memory Leak Issues in NestWhileConditional Gathering of listsHow to find first list element that differs from average of N previous elements by more than a given amount?How to simplify a resistence network and represent the simplifying process?Taking derivative using some variableSort matrix rows and columns while keeping headingCombining Lists in a specified sequenceNeed to add a different random number to each part of the tableBuilding a list of products from the elements in another listEfficient way to iterate over large list and check conditions
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
a = RandomVariate[UniformDistribution[0, 1]];
b = RandomVariate[UniformDistribution[0, 1]];
c = RandomVariate[UniformDistribution[0, 1]];
a + a b + a b c
I want to continue picking random reals in (0,1) and adding the product to the previous sum. How can Mathematica help me here?
Best regards
Geoffrey Critzer
list-manipulation iteration
New contributor
geoffrey 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$
a = RandomVariate[UniformDistribution[0, 1]];
b = RandomVariate[UniformDistribution[0, 1]];
c = RandomVariate[UniformDistribution[0, 1]];
a + a b + a b c
I want to continue picking random reals in (0,1) and adding the product to the previous sum. How can Mathematica help me here?
Best regards
Geoffrey Critzer
list-manipulation iteration
New contributor
geoffrey 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$
a = RandomVariate[UniformDistribution[0, 1]];
b = RandomVariate[UniformDistribution[0, 1]];
c = RandomVariate[UniformDistribution[0, 1]];
a + a b + a b c
I want to continue picking random reals in (0,1) and adding the product to the previous sum. How can Mathematica help me here?
Best regards
Geoffrey Critzer
list-manipulation iteration
New contributor
geoffrey is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
a = RandomVariate[UniformDistribution[0, 1]];
b = RandomVariate[UniformDistribution[0, 1]];
c = RandomVariate[UniformDistribution[0, 1]];
a + a b + a b c
I want to continue picking random reals in (0,1) and adding the product to the previous sum. How can Mathematica help me here?
Best regards
Geoffrey Critzer
list-manipulation iteration
list-manipulation iteration
New contributor
geoffrey is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
geoffrey is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 9 hours ago
C. E.
53.8k3 gold badges103 silver badges211 bronze badges
53.8k3 gold badges103 silver badges211 bronze badges
New contributor
geoffrey is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 9 hours ago
geoffreygeoffrey
261 bronze badge
261 bronze badge
New contributor
geoffrey is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
geoffrey 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$
Here's one way:
SeedRandom[1];
a = RandomVariate[UniformDistribution[0, 1]];
b = RandomVariate[UniformDistribution[0, 1]];
c = RandomVariate[UniformDistribution[0, 1]];
a + a b + a b c
0.980367
SeedRandom[1];
values = RandomVariate[UniformDistribution[0, 1], 3];
Total@FoldList[Times, values]
0.980367
The number 3 can be replaced by any number, however many times you want to iterate.
Here's a procedural solution (with the definition of values as in the previous example):
prod = First[values];
sum = First[values];
Do[
prod *= v;
sum += prod,
v, Rest[values]
];
sum
0.980367
$endgroup$
add a comment |
$begingroup$
C.E.'s answer is great already. I would just like to point out that we may exploit here that floating point addition is usually significantly faster than floating point multiplication that FoldList is just slow, and that multiplication can be cast into addition by applying Log so that we can use Accumulate instead. Morever, we may use vectorized built-in routines for that.
n = 1000000;
values = RandomVariate[UniformDistribution[0, 1], n];
r1 = Total@FoldList[Times, values]; // RepeatedTiming // First
r2 = Total[Exp[Clip[Accumulate[Log[values]], -700., ∞]]]; // RepeatedTiming // First
Max[Abs[r1 - r2]]
0.070
0.0053
0.
For those who wonder what the Clip is for: This is in order to prevent underflow error handling to occurr (the latter slows down things considerably); that happens at about Exp[-709.] or so.
Edit
It is even faster to write a short compiled version of C.E.'s procedure (if do not count in the compilation time):
cf = Compile[x, _Real, 1,
Block[prod = 1., sum = 0.,
Do[prod *= Compile`GetElement[x, i]; sum += r, i, 1, Length[x]];
sum
],
CompilationTarget -> "C"
];
Now:
r3 = cf[values]; // RepeatedTiming // First
Max[Abs[r1 - r3]]
0.0013
1.77636*10^-15
Remark
I formerly claimed that floating point multiplication were slower than floating point addition. As Roman pointed out, that is not correct. While multiplication probably has higher complexity (and with floating point computations, some quite counterintuitive things happen), modern hardware is built such that variuous steps of the multiplication are performed in parallel. Nowadays, there is even a single circuit for fused multiply-add (FMA) and not necessarily any separated addition circuit, so addition and multiplication should take basically the same time.
$endgroup$
1
$begingroup$
On a modern CPU, multiplication is not slower than addition. See, e,g., this discussion that's already ten years old. Single-clock-cycle multipliers have been around for a while now.
$endgroup$
– Roman
5 hours ago
$begingroup$
@Roman Yes, actually, I've read many things like that today, in particular about things that were introduce with the Haswell. Now I am not sure anymore why theAccumulatecode is faster than theFoldList.
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
@Roman I am still working with a Haswell processor and there the situation is such that both ADD and FMA (which is used there for multiplication on this architecture IIRC; since Skylake, FMA is used for both) have the same throughput but ADD has significantly less latency. And that might make the difference: We are not multipling or adding two vectors componentwise (in which case it is only about throughput, not about latency), we are indeed folding here - and that should also depend on latency, IMHO.
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
Maybe the sole reason for the timing differences here is the simple fact that there is no such things as an efficiently implemented multiplicative variant ofAccumulatein Mathematica...
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
Maybe related to this discussion about the memory hogging ofNestWhile? Could it be that in general, nesting and folding are just not that efficient? After all,Accumulate[x]is ten or twenty times faster thanFoldList[Plus, x], whereasFoldList[Times, x]is only imperceptibly slower thanFoldList[Plus, x].
$endgroup$
– Roman
4 hours ago
|
show 1 more comment
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "387"
;
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
);
);
geoffrey 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%2fmathematica.stackexchange.com%2fquestions%2f203562%2fhow-can-i-iterate-this-process%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$
Here's one way:
SeedRandom[1];
a = RandomVariate[UniformDistribution[0, 1]];
b = RandomVariate[UniformDistribution[0, 1]];
c = RandomVariate[UniformDistribution[0, 1]];
a + a b + a b c
0.980367
SeedRandom[1];
values = RandomVariate[UniformDistribution[0, 1], 3];
Total@FoldList[Times, values]
0.980367
The number 3 can be replaced by any number, however many times you want to iterate.
Here's a procedural solution (with the definition of values as in the previous example):
prod = First[values];
sum = First[values];
Do[
prod *= v;
sum += prod,
v, Rest[values]
];
sum
0.980367
$endgroup$
add a comment |
$begingroup$
Here's one way:
SeedRandom[1];
a = RandomVariate[UniformDistribution[0, 1]];
b = RandomVariate[UniformDistribution[0, 1]];
c = RandomVariate[UniformDistribution[0, 1]];
a + a b + a b c
0.980367
SeedRandom[1];
values = RandomVariate[UniformDistribution[0, 1], 3];
Total@FoldList[Times, values]
0.980367
The number 3 can be replaced by any number, however many times you want to iterate.
Here's a procedural solution (with the definition of values as in the previous example):
prod = First[values];
sum = First[values];
Do[
prod *= v;
sum += prod,
v, Rest[values]
];
sum
0.980367
$endgroup$
add a comment |
$begingroup$
Here's one way:
SeedRandom[1];
a = RandomVariate[UniformDistribution[0, 1]];
b = RandomVariate[UniformDistribution[0, 1]];
c = RandomVariate[UniformDistribution[0, 1]];
a + a b + a b c
0.980367
SeedRandom[1];
values = RandomVariate[UniformDistribution[0, 1], 3];
Total@FoldList[Times, values]
0.980367
The number 3 can be replaced by any number, however many times you want to iterate.
Here's a procedural solution (with the definition of values as in the previous example):
prod = First[values];
sum = First[values];
Do[
prod *= v;
sum += prod,
v, Rest[values]
];
sum
0.980367
$endgroup$
Here's one way:
SeedRandom[1];
a = RandomVariate[UniformDistribution[0, 1]];
b = RandomVariate[UniformDistribution[0, 1]];
c = RandomVariate[UniformDistribution[0, 1]];
a + a b + a b c
0.980367
SeedRandom[1];
values = RandomVariate[UniformDistribution[0, 1], 3];
Total@FoldList[Times, values]
0.980367
The number 3 can be replaced by any number, however many times you want to iterate.
Here's a procedural solution (with the definition of values as in the previous example):
prod = First[values];
sum = First[values];
Do[
prod *= v;
sum += prod,
v, Rest[values]
];
sum
0.980367
edited 9 hours ago
answered 9 hours ago
C. E.C. E.
53.8k3 gold badges103 silver badges211 bronze badges
53.8k3 gold badges103 silver badges211 bronze badges
add a comment |
add a comment |
$begingroup$
C.E.'s answer is great already. I would just like to point out that we may exploit here that floating point addition is usually significantly faster than floating point multiplication that FoldList is just slow, and that multiplication can be cast into addition by applying Log so that we can use Accumulate instead. Morever, we may use vectorized built-in routines for that.
n = 1000000;
values = RandomVariate[UniformDistribution[0, 1], n];
r1 = Total@FoldList[Times, values]; // RepeatedTiming // First
r2 = Total[Exp[Clip[Accumulate[Log[values]], -700., ∞]]]; // RepeatedTiming // First
Max[Abs[r1 - r2]]
0.070
0.0053
0.
For those who wonder what the Clip is for: This is in order to prevent underflow error handling to occurr (the latter slows down things considerably); that happens at about Exp[-709.] or so.
Edit
It is even faster to write a short compiled version of C.E.'s procedure (if do not count in the compilation time):
cf = Compile[x, _Real, 1,
Block[prod = 1., sum = 0.,
Do[prod *= Compile`GetElement[x, i]; sum += r, i, 1, Length[x]];
sum
],
CompilationTarget -> "C"
];
Now:
r3 = cf[values]; // RepeatedTiming // First
Max[Abs[r1 - r3]]
0.0013
1.77636*10^-15
Remark
I formerly claimed that floating point multiplication were slower than floating point addition. As Roman pointed out, that is not correct. While multiplication probably has higher complexity (and with floating point computations, some quite counterintuitive things happen), modern hardware is built such that variuous steps of the multiplication are performed in parallel. Nowadays, there is even a single circuit for fused multiply-add (FMA) and not necessarily any separated addition circuit, so addition and multiplication should take basically the same time.
$endgroup$
1
$begingroup$
On a modern CPU, multiplication is not slower than addition. See, e,g., this discussion that's already ten years old. Single-clock-cycle multipliers have been around for a while now.
$endgroup$
– Roman
5 hours ago
$begingroup$
@Roman Yes, actually, I've read many things like that today, in particular about things that were introduce with the Haswell. Now I am not sure anymore why theAccumulatecode is faster than theFoldList.
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
@Roman I am still working with a Haswell processor and there the situation is such that both ADD and FMA (which is used there for multiplication on this architecture IIRC; since Skylake, FMA is used for both) have the same throughput but ADD has significantly less latency. And that might make the difference: We are not multipling or adding two vectors componentwise (in which case it is only about throughput, not about latency), we are indeed folding here - and that should also depend on latency, IMHO.
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
Maybe the sole reason for the timing differences here is the simple fact that there is no such things as an efficiently implemented multiplicative variant ofAccumulatein Mathematica...
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
Maybe related to this discussion about the memory hogging ofNestWhile? Could it be that in general, nesting and folding are just not that efficient? After all,Accumulate[x]is ten or twenty times faster thanFoldList[Plus, x], whereasFoldList[Times, x]is only imperceptibly slower thanFoldList[Plus, x].
$endgroup$
– Roman
4 hours ago
|
show 1 more comment
$begingroup$
C.E.'s answer is great already. I would just like to point out that we may exploit here that floating point addition is usually significantly faster than floating point multiplication that FoldList is just slow, and that multiplication can be cast into addition by applying Log so that we can use Accumulate instead. Morever, we may use vectorized built-in routines for that.
n = 1000000;
values = RandomVariate[UniformDistribution[0, 1], n];
r1 = Total@FoldList[Times, values]; // RepeatedTiming // First
r2 = Total[Exp[Clip[Accumulate[Log[values]], -700., ∞]]]; // RepeatedTiming // First
Max[Abs[r1 - r2]]
0.070
0.0053
0.
For those who wonder what the Clip is for: This is in order to prevent underflow error handling to occurr (the latter slows down things considerably); that happens at about Exp[-709.] or so.
Edit
It is even faster to write a short compiled version of C.E.'s procedure (if do not count in the compilation time):
cf = Compile[x, _Real, 1,
Block[prod = 1., sum = 0.,
Do[prod *= Compile`GetElement[x, i]; sum += r, i, 1, Length[x]];
sum
],
CompilationTarget -> "C"
];
Now:
r3 = cf[values]; // RepeatedTiming // First
Max[Abs[r1 - r3]]
0.0013
1.77636*10^-15
Remark
I formerly claimed that floating point multiplication were slower than floating point addition. As Roman pointed out, that is not correct. While multiplication probably has higher complexity (and with floating point computations, some quite counterintuitive things happen), modern hardware is built such that variuous steps of the multiplication are performed in parallel. Nowadays, there is even a single circuit for fused multiply-add (FMA) and not necessarily any separated addition circuit, so addition and multiplication should take basically the same time.
$endgroup$
1
$begingroup$
On a modern CPU, multiplication is not slower than addition. See, e,g., this discussion that's already ten years old. Single-clock-cycle multipliers have been around for a while now.
$endgroup$
– Roman
5 hours ago
$begingroup$
@Roman Yes, actually, I've read many things like that today, in particular about things that were introduce with the Haswell. Now I am not sure anymore why theAccumulatecode is faster than theFoldList.
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
@Roman I am still working with a Haswell processor and there the situation is such that both ADD and FMA (which is used there for multiplication on this architecture IIRC; since Skylake, FMA is used for both) have the same throughput but ADD has significantly less latency. And that might make the difference: We are not multipling or adding two vectors componentwise (in which case it is only about throughput, not about latency), we are indeed folding here - and that should also depend on latency, IMHO.
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
Maybe the sole reason for the timing differences here is the simple fact that there is no such things as an efficiently implemented multiplicative variant ofAccumulatein Mathematica...
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
Maybe related to this discussion about the memory hogging ofNestWhile? Could it be that in general, nesting and folding are just not that efficient? After all,Accumulate[x]is ten or twenty times faster thanFoldList[Plus, x], whereasFoldList[Times, x]is only imperceptibly slower thanFoldList[Plus, x].
$endgroup$
– Roman
4 hours ago
|
show 1 more comment
$begingroup$
C.E.'s answer is great already. I would just like to point out that we may exploit here that floating point addition is usually significantly faster than floating point multiplication that FoldList is just slow, and that multiplication can be cast into addition by applying Log so that we can use Accumulate instead. Morever, we may use vectorized built-in routines for that.
n = 1000000;
values = RandomVariate[UniformDistribution[0, 1], n];
r1 = Total@FoldList[Times, values]; // RepeatedTiming // First
r2 = Total[Exp[Clip[Accumulate[Log[values]], -700., ∞]]]; // RepeatedTiming // First
Max[Abs[r1 - r2]]
0.070
0.0053
0.
For those who wonder what the Clip is for: This is in order to prevent underflow error handling to occurr (the latter slows down things considerably); that happens at about Exp[-709.] or so.
Edit
It is even faster to write a short compiled version of C.E.'s procedure (if do not count in the compilation time):
cf = Compile[x, _Real, 1,
Block[prod = 1., sum = 0.,
Do[prod *= Compile`GetElement[x, i]; sum += r, i, 1, Length[x]];
sum
],
CompilationTarget -> "C"
];
Now:
r3 = cf[values]; // RepeatedTiming // First
Max[Abs[r1 - r3]]
0.0013
1.77636*10^-15
Remark
I formerly claimed that floating point multiplication were slower than floating point addition. As Roman pointed out, that is not correct. While multiplication probably has higher complexity (and with floating point computations, some quite counterintuitive things happen), modern hardware is built such that variuous steps of the multiplication are performed in parallel. Nowadays, there is even a single circuit for fused multiply-add (FMA) and not necessarily any separated addition circuit, so addition and multiplication should take basically the same time.
$endgroup$
C.E.'s answer is great already. I would just like to point out that we may exploit here that floating point addition is usually significantly faster than floating point multiplication that FoldList is just slow, and that multiplication can be cast into addition by applying Log so that we can use Accumulate instead. Morever, we may use vectorized built-in routines for that.
n = 1000000;
values = RandomVariate[UniformDistribution[0, 1], n];
r1 = Total@FoldList[Times, values]; // RepeatedTiming // First
r2 = Total[Exp[Clip[Accumulate[Log[values]], -700., ∞]]]; // RepeatedTiming // First
Max[Abs[r1 - r2]]
0.070
0.0053
0.
For those who wonder what the Clip is for: This is in order to prevent underflow error handling to occurr (the latter slows down things considerably); that happens at about Exp[-709.] or so.
Edit
It is even faster to write a short compiled version of C.E.'s procedure (if do not count in the compilation time):
cf = Compile[x, _Real, 1,
Block[prod = 1., sum = 0.,
Do[prod *= Compile`GetElement[x, i]; sum += r, i, 1, Length[x]];
sum
],
CompilationTarget -> "C"
];
Now:
r3 = cf[values]; // RepeatedTiming // First
Max[Abs[r1 - r3]]
0.0013
1.77636*10^-15
Remark
I formerly claimed that floating point multiplication were slower than floating point addition. As Roman pointed out, that is not correct. While multiplication probably has higher complexity (and with floating point computations, some quite counterintuitive things happen), modern hardware is built such that variuous steps of the multiplication are performed in parallel. Nowadays, there is even a single circuit for fused multiply-add (FMA) and not necessarily any separated addition circuit, so addition and multiplication should take basically the same time.
edited 4 hours ago
answered 9 hours ago
Henrik SchumacherHenrik Schumacher
67k5 gold badges95 silver badges185 bronze badges
67k5 gold badges95 silver badges185 bronze badges
1
$begingroup$
On a modern CPU, multiplication is not slower than addition. See, e,g., this discussion that's already ten years old. Single-clock-cycle multipliers have been around for a while now.
$endgroup$
– Roman
5 hours ago
$begingroup$
@Roman Yes, actually, I've read many things like that today, in particular about things that were introduce with the Haswell. Now I am not sure anymore why theAccumulatecode is faster than theFoldList.
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
@Roman I am still working with a Haswell processor and there the situation is such that both ADD and FMA (which is used there for multiplication on this architecture IIRC; since Skylake, FMA is used for both) have the same throughput but ADD has significantly less latency. And that might make the difference: We are not multipling or adding two vectors componentwise (in which case it is only about throughput, not about latency), we are indeed folding here - and that should also depend on latency, IMHO.
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
Maybe the sole reason for the timing differences here is the simple fact that there is no such things as an efficiently implemented multiplicative variant ofAccumulatein Mathematica...
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
Maybe related to this discussion about the memory hogging ofNestWhile? Could it be that in general, nesting and folding are just not that efficient? After all,Accumulate[x]is ten or twenty times faster thanFoldList[Plus, x], whereasFoldList[Times, x]is only imperceptibly slower thanFoldList[Plus, x].
$endgroup$
– Roman
4 hours ago
|
show 1 more comment
1
$begingroup$
On a modern CPU, multiplication is not slower than addition. See, e,g., this discussion that's already ten years old. Single-clock-cycle multipliers have been around for a while now.
$endgroup$
– Roman
5 hours ago
$begingroup$
@Roman Yes, actually, I've read many things like that today, in particular about things that were introduce with the Haswell. Now I am not sure anymore why theAccumulatecode is faster than theFoldList.
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
@Roman I am still working with a Haswell processor and there the situation is such that both ADD and FMA (which is used there for multiplication on this architecture IIRC; since Skylake, FMA is used for both) have the same throughput but ADD has significantly less latency. And that might make the difference: We are not multipling or adding two vectors componentwise (in which case it is only about throughput, not about latency), we are indeed folding here - and that should also depend on latency, IMHO.
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
Maybe the sole reason for the timing differences here is the simple fact that there is no such things as an efficiently implemented multiplicative variant ofAccumulatein Mathematica...
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
Maybe related to this discussion about the memory hogging ofNestWhile? Could it be that in general, nesting and folding are just not that efficient? After all,Accumulate[x]is ten or twenty times faster thanFoldList[Plus, x], whereasFoldList[Times, x]is only imperceptibly slower thanFoldList[Plus, x].
$endgroup$
– Roman
4 hours ago
1
1
$begingroup$
On a modern CPU, multiplication is not slower than addition. See, e,g., this discussion that's already ten years old. Single-clock-cycle multipliers have been around for a while now.
$endgroup$
– Roman
5 hours ago
$begingroup$
On a modern CPU, multiplication is not slower than addition. See, e,g., this discussion that's already ten years old. Single-clock-cycle multipliers have been around for a while now.
$endgroup$
– Roman
5 hours ago
$begingroup$
@Roman Yes, actually, I've read many things like that today, in particular about things that were introduce with the Haswell. Now I am not sure anymore why the
Accumulate code is faster than the FoldList.$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
@Roman Yes, actually, I've read many things like that today, in particular about things that were introduce with the Haswell. Now I am not sure anymore why the
Accumulate code is faster than the FoldList.$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
@Roman I am still working with a Haswell processor and there the situation is such that both ADD and FMA (which is used there for multiplication on this architecture IIRC; since Skylake, FMA is used for both) have the same throughput but ADD has significantly less latency. And that might make the difference: We are not multipling or adding two vectors componentwise (in which case it is only about throughput, not about latency), we are indeed folding here - and that should also depend on latency, IMHO.
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
@Roman I am still working with a Haswell processor and there the situation is such that both ADD and FMA (which is used there for multiplication on this architecture IIRC; since Skylake, FMA is used for both) have the same throughput but ADD has significantly less latency. And that might make the difference: We are not multipling or adding two vectors componentwise (in which case it is only about throughput, not about latency), we are indeed folding here - and that should also depend on latency, IMHO.
$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
Maybe the sole reason for the timing differences here is the simple fact that there is no such things as an efficiently implemented multiplicative variant of
Accumulate in Mathematica...$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
Maybe the sole reason for the timing differences here is the simple fact that there is no such things as an efficiently implemented multiplicative variant of
Accumulate in Mathematica...$endgroup$
– Henrik Schumacher
4 hours ago
$begingroup$
Maybe related to this discussion about the memory hogging of
NestWhile? Could it be that in general, nesting and folding are just not that efficient? After all, Accumulate[x] is ten or twenty times faster than FoldList[Plus, x], whereas FoldList[Times, x] is only imperceptibly slower than FoldList[Plus, x].$endgroup$
– Roman
4 hours ago
$begingroup$
Maybe related to this discussion about the memory hogging of
NestWhile? Could it be that in general, nesting and folding are just not that efficient? After all, Accumulate[x] is ten or twenty times faster than FoldList[Plus, x], whereas FoldList[Times, x] is only imperceptibly slower than FoldList[Plus, x].$endgroup$
– Roman
4 hours ago
|
show 1 more comment
geoffrey is a new contributor. Be nice, and check out our Code of Conduct.
geoffrey is a new contributor. Be nice, and check out our Code of Conduct.
geoffrey is a new contributor. Be nice, and check out our Code of Conduct.
geoffrey is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Mathematica 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%2fmathematica.stackexchange.com%2fquestions%2f203562%2fhow-can-i-iterate-this-process%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