Opened 13 years ago
Last modified 7 years ago
#3925 needs_work enhancement
[with SPKG, needs work] Wrap Bernstein 's primegen
Reported by: | robertwb | Owned by: | was |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | number theory | Keywords: | |
Cc: | mvngu, kevin.stueve | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Attachments (3)
Change History (17)
comment:1 Changed 12 years ago by
comment:2 Changed 12 years ago by
- Cc mvngu added
comment:3 Changed 12 years ago by
- Milestone changed from sage-wishlist to sage-4.1.1
Changed 12 years ago by
Changed 12 years ago by
comment:4 Changed 12 years ago by
- Summary changed from Wrap Bernstein 's primegen to [with SPKG, needs review] Wrap Bernstein 's primegen
I've added an attempt at an .spkg for primegen-0.97 as an attachment, and also took the liberty of patching (untested...) spkg/install and spkg/standard/deps to build it automatically when installing sage. (In the 'spkg_deps' patch.)
I'm not entirely confident the build system of the library will work everywhere, since it is rather non-standard, but hopefully it is portable enough.
The library is tiny, with the .spkg only 32KB, and the compiled (Linux x86_64) library only 17KB.
Timing:
def f(): P = Primes() for p in P: if p > 10^8: break time f()
goes from 84.17s (without this spkg+patch) to 20.77s (with spkg+patch) on a 2GHz Opteron.
Changed 12 years ago by
comment:5 Changed 12 years ago by
Hello Willem. I successfully installed the spkg and the second patch but I don't know how to install the first patch as it changes files not in the usual code tree. If you tell me how, I would like to test this. -- John
comment:6 follow-up: ↓ 7 Changed 12 years ago by
Hi John. The first patch isn't necessary to use the spkg. It's only for making a fresh 'make' of sage automatically build the spkg. I'm not too sure sure if that patch is right, actually; that part should probably be left to a release manager.
comment:7 in reply to: ↑ 6 Changed 12 years ago by
Replying to wjp:
Hi John. The first patch isn't necessary to use the spkg. It's only for making a fresh 'make' of sage automatically build the spkg. I'm not too sure sure if that patch is right, actually; that part should probably be left to a release manager.
OK, I'll have another go sometime this weekend. I'm glad about the first patch, since I'm not really competent to say if it's right (though it looks ok).
comment:8 Changed 12 years ago by
To adopt this spkg as part of Sage proper would need a vote on sage-devel. I suggest that wjp helps that process by collecting some data (before and after). For example:
sage: time P = prime_range(10^8) CPU times: user 1.83 s, sys: 0.50 s, total: 2.32 s Wall time: 2.33 s sage: len(P) 5761455
but this does not use the new PrimeGen? class. I tried this (with the new spkg + patch):
sage: pg=Primes().pg sage: pg.reset() sage: N=pg.count(10^8) sage: pg.reset() sage: time P=[pg.next() for _ in range(N)] CPU times: user 4.98 s, sys: 0.03 s, total: 5.01 s Wall time: 5.02 s
which is slower but it's using a more stupid method to collect the primes that in prime_range().
comment:9 Changed 12 years ago by
- Summary changed from [with SPKG, needs review] Wrap Bernstein 's primegen to [with SPKG, needs work] Wrap Bernstein 's primegen
Changing this to "needs work" given John's latest comments. Note that "work" here would mean making the case to sage-devel that the spkg should be adopted, and asking for a vote.
comment:10 Changed 12 years ago by
- Cc kevin.stueve added
- Report Upstream set to N/A
comment:11 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:12 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:13 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:14 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
I added some checks and doctests, and made Primes() use this.
This is still a work-in-progress. TODO: