Subtracting composits from wheel for primes in Haskell
$begingroup$
Calculating many remainders for each prime and composite consumes more time.
I do use a factoring function to find factors of single values.
When I use a factoring function to find lists of primes, I use a wheel.
A wheel exploits composite values punctuating an otherwise prime sequence.
The primary advantage of a wheel is reducing significantly, the candidate list and so processing.
My wheel eliminates 2, 3, 5 and 7 multiples from the a list. For the longest time, is used only elimination of 2s, 3s and 5s because the wheel list is only 8 values.
Take the deltas from 11,13,17,19,23,29,31,39 or add 30 to each of the previous 8 values for subsequent values.
Deltas from 48 or more of the 'no 2,s,3s,5s' will produce the no 7s wheel list.
What should be faster is subtraction of one list from another where the calc is compare and once only for each.
wl = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
-- the so-called wheel: the recurring pattern in a composite punctuated list
n7sl = scanl (+) 11 $ cycle wl -- infinite
-- short list of primes with no 2's, 3's 5's or 7's; 77%+ reduced
n7s = take 150 $ n7sl
-- diagonalize and limit the factor's composite list
lls i y = drop i.take y $ n7sl
-- substract the 1st list from the 2nd, infinite list
rms _ = -- stop when first list is exhausted
rms n@(x:xs) p@(y:ys)
| x==y = rms xs ys
| x>y = y:rms n ys
| y>x = rms xs p
-- generate the composite list
comps _ _ _ _ =
comps (n:ns) y i b = comps ns (lls (i+1) y) y (i+1) b
comps k@(n:ns) (r:rs) y i b
| m>b =comps ns (lls (i+1) y) y (i+1) b
| m<=b =m:comps k rs y i b
where m = n*r
-- the result of `comps` is not just a diagonalization but 2, top & irregular bottom
-- `comps` is maybe necessary to stop when the limit of a list is reached
-- otherwise, I was using a list comprehension which is way less complicated
-- `comps` has to many parameters so this to reduce it to 1
-- it will be subtracted the fixed length wheel numbers and the lazy wheel
comp1 n =sort $ comps n7s (lls 0 n) n 0 (11*(last.take n $ n7sl))
-- put everything together go generate primes
last $ rms (comp1 5000) n7sl
240641
(0.12 secs, 65,219,592 bytes)
last $ rms (comp1 10000) n7sl
481249
(0.24 secs, 143,743,944 bytes)
last $ rms (comp1 15000) n7sl
721891
(0.37 secs, 220,099,904 bytes)
Question is this better that factoring? Is there a better way to generate multiples without multiplying in comps or list comprehensions?
Any prime list I generate excludes 2,3,5 & 7 because they are misbehaved, irregular and to well known.
haskell primes
asked 8 hours ago
fp_morafp_mora
1064
$endgroup$
add a comment |
$begingroup$
Calculating many remainders for each prime and composite consumes more time.
I do use a factoring function to find factors of single values.
When I use a factoring function to find lists of primes, I use a wheel.
A wheel exploits composite values punctuating an otherwise prime sequence.
The primary advantage of a wheel is reducing significantly, the candidate list and so processing.
My wheel eliminates 2, 3, 5 and 7 multiples from the a list. For the longest time, is used only elimination of 2s, 3s and 5s because the wheel list is only 8 values.
Take the deltas from 11,13,17,19,23,29,31,39 or add 30 to each of the previous 8 values for subsequent values.
Deltas from 48 or more of the 'no 2,s,3s,5s' will produce the no 7s wheel list.
What should be faster is subtraction of one list from another where the calc is compare and once only for each.
wl = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
-- the so-called wheel: the recurring pattern in a composite punctuated list
n7sl = scanl (+) 11 $ cycle wl -- infinite
-- short list of primes with no 2's, 3's 5's or 7's; 77%+ reduced
n7s = take 150 $ n7sl
-- diagonalize and limit the factor's composite list
lls i y = drop i.take y $ n7sl
-- substract the 1st list from the 2nd, infinite list
rms _ = -- stop when first list is exhausted
rms n@(x:xs) p@(y:ys)
| x==y = rms xs ys
| x>y = y:rms n ys
| y>x = rms xs p
-- generate the composite list
comps _ _ _ _ =
comps (n:ns) y i b = comps ns (lls (i+1) y) y (i+1) b
comps k@(n:ns) (r:rs) y i b
| m>b =comps ns (lls (i+1) y) y (i+1) b
| m<=b =m:comps k rs y i b
where m = n*r
-- the result of `comps` is not just a diagonalization but 2, top & irregular bottom
-- `comps` is maybe necessary to stop when the limit of a list is reached
-- otherwise, I was using a list comprehension which is way less complicated
-- `comps` has to many parameters so this to reduce it to 1
-- it will be subtracted the fixed length wheel numbers and the lazy wheel
comp1 n =sort $ comps n7s (lls 0 n) n 0 (11*(last.take n $ n7sl))
-- put everything together go generate primes
last $ rms (comp1 5000) n7sl
240641
(0.12 secs, 65,219,592 bytes)
last $ rms (comp1 10000) n7sl
481249
(0.24 secs, 143,743,944 bytes)
last $ rms (comp1 15000) n7sl
721891
(0.37 secs, 220,099,904 bytes)
Question is this better that factoring? Is there a better way to generate multiples without multiplying in comps or list comprehensions?
Any prime list I generate excludes 2,3,5 & 7 because they are misbehaved, irregular and to well known.
haskell primes
asked 8 hours ago
fp_morafp_mora
1064
$endgroup$
$begingroup$
Well, I had residuals.rmswas written to remove 7s from 2s,3s,5s list. Remove sevens:rmsThen, incompsI had had trouble with the multiple. It was in a where statement b/c it occurs 3 times. Then, after fixing another problem forgot to put it back.
$endgroup$
– fp_mora
5 hours ago
add a comment |
$begingroup$
Calculating many remainders for each prime and composite consumes more time.
I do use a factoring function to find factors of single values.
When I use a factoring function to find lists of primes, I use a wheel.
A wheel exploits composite values punctuating an otherwise prime sequence.
The primary advantage of a wheel is reducing significantly, the candidate list and so processing.
My wheel eliminates 2, 3, 5 and 7 multiples from the a list. For the longest time, is used only elimination of 2s, 3s and 5s because the wheel list is only 8 values.
Take the deltas from 11,13,17,19,23,29,31,39 or add 30 to each of the previous 8 values for subsequent values.
Deltas from 48 or more of the 'no 2,s,3s,5s' will produce the no 7s wheel list.
What should be faster is subtraction of one list from another where the calc is compare and once only for each.
wl = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
-- the so-called wheel: the recurring pattern in a composite punctuated list
n7sl = scanl (+) 11 $ cycle wl -- infinite
-- short list of primes with no 2's, 3's 5's or 7's; 77%+ reduced
n7s = take 150 $ n7sl
-- diagonalize and limit the factor's composite list
lls i y = drop i.take y $ n7sl
-- substract the 1st list from the 2nd, infinite list
rms _ = -- stop when first list is exhausted
rms n@(x:xs) p@(y:ys)
| x==y = rms xs ys
| x>y = y:rms n ys
| y>x = rms xs p
-- generate the composite list
comps _ _ _ _ =
comps (n:ns) y i b = comps ns (lls (i+1) y) y (i+1) b
comps k@(n:ns) (r:rs) y i b
| m>b =comps ns (lls (i+1) y) y (i+1) b
| m<=b =m:comps k rs y i b
where m = n*r
-- the result of `comps` is not just a diagonalization but 2, top & irregular bottom
-- `comps` is maybe necessary to stop when the limit of a list is reached
-- otherwise, I was using a list comprehension which is way less complicated
-- `comps` has to many parameters so this to reduce it to 1
-- it will be subtracted the fixed length wheel numbers and the lazy wheel
comp1 n =sort $ comps n7s (lls 0 n) n 0 (11*(last.take n $ n7sl))
-- put everything together go generate primes
last $ rms (comp1 5000) n7sl
240641
(0.12 secs, 65,219,592 bytes)
last $ rms (comp1 10000) n7sl
481249
(0.24 secs, 143,743,944 bytes)
last $ rms (comp1 15000) n7sl
721891
(0.37 secs, 220,099,904 bytes)
Question is this better that factoring? Is there a better way to generate multiples without multiplying in comps or list comprehensions?
Any prime list I generate excludes 2,3,5 & 7 because they are misbehaved, irregular and to well known.
haskell primes
asked 8 hours ago
fp_morafp_mora
1064
$endgroup$
Calculating many remainders for each prime and composite consumes more time.
I do use a factoring function to find factors of single values.
When I use a factoring function to find lists of primes, I use a wheel.
A wheel exploits composite values punctuating an otherwise prime sequence.
The primary advantage of a wheel is reducing significantly, the candidate list and so processing.
My wheel eliminates 2, 3, 5 and 7 multiples from the a list. For the longest time, is used only elimination of 2s, 3s and 5s because the wheel list is only 8 values.
Take the deltas from 11,13,17,19,23,29,31,39 or add 30 to each of the previous 8 values for subsequent values.
Deltas from 48 or more of the 'no 2,s,3s,5s' will produce the no 7s wheel list.
What should be faster is subtraction of one list from another where the calc is compare and once only for each.
wl = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
-- the so-called wheel: the recurring pattern in a composite punctuated list
n7sl = scanl (+) 11 $ cycle wl -- infinite
-- short list of primes with no 2's, 3's 5's or 7's; 77%+ reduced
n7s = take 150 $ n7sl
-- diagonalize and limit the factor's composite list
lls i y = drop i.take y $ n7sl
-- substract the 1st list from the 2nd, infinite list
rms _ = -- stop when first list is exhausted
rms n@(x:xs) p@(y:ys)
| x==y = rms xs ys
| x>y = y:rms n ys
| y>x = rms xs p
-- generate the composite list
comps _ _ _ _ =
comps (n:ns) y i b = comps ns (lls (i+1) y) y (i+1) b
comps k@(n:ns) (r:rs) y i b
| m>b =comps ns (lls (i+1) y) y (i+1) b
| m<=b =m:comps k rs y i b
where m = n*r
-- the result of `comps` is not just a diagonalization but 2, top & irregular bottom
-- `comps` is maybe necessary to stop when the limit of a list is reached
-- otherwise, I was using a list comprehension which is way less complicated
-- `comps` has to many parameters so this to reduce it to 1
-- it will be subtracted the fixed length wheel numbers and the lazy wheel
comp1 n =sort $ comps n7s (lls 0 n) n 0 (11*(last.take n $ n7sl))
-- put everything together go generate primes
last $ rms (comp1 5000) n7sl
240641
(0.12 secs, 65,219,592 bytes)
last $ rms (comp1 10000) n7sl
481249
(0.24 secs, 143,743,944 bytes)
last $ rms (comp1 15000) n7sl
721891
(0.37 secs, 220,099,904 bytes)
Question is this better that factoring? Is there a better way to generate multiples without multiplying in comps or list comprehensions?
Any prime list I generate excludes 2,3,5 & 7 because they are misbehaved, irregular and to well known.
haskell primes
haskell primes
asked 8 hours ago
fp_morafp_mora
1064
asked 8 hours ago
fp_morafp_mora
1064
edited 5 hours ago
fp_mora
asked 8 hours ago
fp_morafp_mora
1064
asked 8 hours ago
fp_morafp_mora
1064
asked 8 hours ago
fp_morafp_mora
1064
1064
$begingroup$
Well, I had residuals.rmswas written to remove 7s from 2s,3s,5s list. Remove sevens:rmsThen, incompsI had had trouble with the multiple. It was in a where statement b/c it occurs 3 times. Then, after fixing another problem forgot to put it back.
$endgroup$
– fp_mora
5 hours ago
add a comment |
$begingroup$
Well, I had residuals.rmswas written to remove 7s from 2s,3s,5s list. Remove sevens:rmsThen, incompsI had had trouble with the multiple. It was in a where statement b/c it occurs 3 times. Then, after fixing another problem forgot to put it back.
$endgroup$
– fp_mora
5 hours ago
$begingroup$
Well, I had residuals.
rms was written to remove 7s from 2s,3s,5s list. Remove sevens: rms Then, in comps I had had trouble with the multiple. It was in a where statement b/c it occurs 3 times. Then, after fixing another problem forgot to put it back.$endgroup$
– fp_mora
5 hours ago
$begingroup$
Well, I had residuals.
rms was written to remove 7s from 2s,3s,5s list. Remove sevens: rms Then, in comps I had had trouble with the multiple. It was in a where statement b/c it occurs 3 times. Then, after fixing another problem forgot to put it back.$endgroup$
– fp_mora
5 hours ago
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.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
});
}
});
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%2f216354%2fsubtracting-composits-from-wheel-for-primes-in-haskell%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to 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.
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%2f216354%2fsubtracting-composits-from-wheel-for-primes-in-haskell%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
$begingroup$
Well, I had residuals.
rmswas written to remove 7s from 2s,3s,5s list. Remove sevens:rmsThen, incompsI had had trouble with the multiple. It was in a where statement b/c it occurs 3 times. Then, after fixing another problem forgot to put it back.$endgroup$
– fp_mora
5 hours ago