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
If the first law of thermodynamics ensures conservation of energy, why does it allow systems to lose energy?
Algorithms vs LP or MIP
Why is less being run unnecessarily by git?
What to say to a student who has failed?
Cross-referencing enumerate item
Why don't electrons take the shorter path in coils?
Why did MS-DOS applications built using Turbo Pascal fail to start with a division by zero error on faster systems?
Accent on í misaligned in bibliography / citation
Was there ever a treaty between 2 entities with significantly different translations to the detriment of one party?
Can pay be witheld for hours cleaning up after closing time?
How to use "Du hast/ Du hattest'?
Using `With[...]` with a list specification as a variable
Does norwegian.no airline overbook flights?
Why is my Earth simulation slower than the reality?
Efficiently pathfinding many flocking enemies around obstacles
Did a flight controller ever answer Flight with a no-go?
Would it be possible to have a GMO that produces chocolate?
Singleton Design Pattern implementation in a not traditional way
Rule based coloured background for labeling in QGIS
Numbers Decrease while Letters Increase
Shouldn't the "credit score" prevent Americans from going deeper and deeper into personal debt?
Why were the crew so desperate to catch Truman and return him to Seahaven?
Notepad++ - How to find multiple values on the same line in any permutation
Are illustrations in novels frowned upon?
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
$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
$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
$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
edited Aug 10 at 14:33
C. E.
54.2k3 gold badges105 silver badges213 bronze badges
54.2k3 gold badges105 silver badges213 bronze badges
asked Aug 10 at 14:30
geoffreygeoffrey
383 bronze badges
383 bronze badges
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$
2
$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
Aug 10 at 19:04
$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
Aug 10 at 19:40
$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
Aug 10 at 19:43
$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
Aug 10 at 19:44
$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
Aug 10 at 19:44
|
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
);
);
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 Aug 10 at 14:59
answered Aug 10 at 14:39
C. E.C. E.
54.2k3 gold badges105 silver badges213 bronze badges
54.2k3 gold badges105 silver badges213 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$
2
$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
Aug 10 at 19:04
$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
Aug 10 at 19:40
$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
Aug 10 at 19:43
$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
Aug 10 at 19:44
$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
Aug 10 at 19:44
|
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$
2
$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
Aug 10 at 19:04
$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
Aug 10 at 19:40
$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
Aug 10 at 19:43
$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
Aug 10 at 19:44
$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
Aug 10 at 19:44
|
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 Aug 10 at 20:07
answered Aug 10 at 15:09
Henrik SchumacherHenrik Schumacher
67.5k5 gold badges96 silver badges186 bronze badges
67.5k5 gold badges96 silver badges186 bronze badges
2
$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
Aug 10 at 19:04
$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
Aug 10 at 19:40
$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
Aug 10 at 19:43
$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
Aug 10 at 19:44
$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
Aug 10 at 19:44
|
show 1 more comment
2
$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
Aug 10 at 19:04
$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
Aug 10 at 19:40
$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
Aug 10 at 19:43
$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
Aug 10 at 19:44
$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
Aug 10 at 19:44
2
2
$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
Aug 10 at 19:04
$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
Aug 10 at 19:04
$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
Aug 10 at 19:40
$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
Aug 10 at 19:40
$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
Aug 10 at 19:43
$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
Aug 10 at 19:43
$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
Aug 10 at 19:44
$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
Aug 10 at 19:44
$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
Aug 10 at 19:44
$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
Aug 10 at 19:44
|
show 1 more comment
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