-
Notifications
You must be signed in to change notification settings - Fork 35
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Prime factorization? #147
Comments
Below are the times I got when using janet 1.30.0:
FWIW, results were similar with janet's 7049f658. /me is looking forward to upgrading hardware... |
After janet-lang/janet#1249 this became about 15% faster: pseudoprimes 1.004s, 41.61µs/body
small integers 0.331s, 3.308µs/body and the strange thing is, I don't even use any compare functions... not directly anyway. |
With that janet (7475362c), I got:
So there appears to be some speedup here too. |
I've updated to handle > (factor 123456789123)
@[3 12049 3415409]
> (factor (int/s64 123456789123))
@[<core/s64 3> <core/s64 12049> <core/s64 3415409>] It has become a bit slower, but that was expected. Not too bad, though: pseudoprimes 1.001s, 42.47µs/body
small integers 0.428s, 4.278µs/body The merge sort became a bit messy, because (defn- merge-sorted
"merge two sorted arrays"
[a b]
(def len (+ (length a) (length b)))
(def c (array/new-filled len))
(var [i j] [0 0])
(forv k 0 len
(let [u (get a i)
v (get b j)]
(if (not= nil u)
(if (not= nil v)
(if (compare< u v)
(do (put c k u) (++ i))
(do (put c k v) (++ j)))
(do (put c k u) (++ i)))
(do (put c k v) (++ j)))))
c) In particular, the repetition is a somewhat ugly. If someone could help clean that up, that'd be really nice 😆 I think that |
Didn't have luck reducing duplication, but possibly the following is a bit easier to read? (defn- merge-sorted-2
"merge two sorted arrays"
[a b]
(def len (+ (length a) (length b)))
(def c (array/new-filled len))
(var [i j] [0 0])
(forv k 0 len
(def [u v] [(get a i) (get b j)])
(cond
(nil? u) (do (put c k v) (++ j))
(nil? v) (do (put c k u) (++ i))
(compare< u v) (do (put c k u) (++ i))
(do (put c k v) (++ j))))
c) or may be without the repeated destructuring in the loop could be better? |
Definitely nicer to look at 👍
Destructuring is already compiler optimized 😃 |
I had another version which is longer and not as nice to view, but may be it does less nil-related comparisons sometimes... (defn- merge-sorted-3
"merge two sorted arrays"
[a b]
(def len (+ (length a) (length b)))
(def c (array/new-filled len))
(var [i j k] [0 0 0])
(var [u v] [(get a i) (get b j)])
(while (and (not= nil u) (not= nil v))
(if (compare< u v)
(do
(put c k u)
(++ i)
(set u (get a i)))
(do
(put c k v)
(++ j)
(set v (get b j))))
(++ k))
(cond
(nil? u)
(while (< k len)
(put c k v)
(++ j)
(set v (get b j))
(++ k))
#
(nil? v)
(while (< k len)
(put c k u)
(++ i)
(set u (get a i))
(++ k)))
c) Possibly not worth it. |
I am sure it would be excellent :-). |
Switching |
If there were an (defn- merge-sorted-4
"merge two sorted arrays"
[a b]
(def len (+ (length a) (length b)))
(def c (array/new-filled len))
(var [i j k] [0 0 0])
(var [u v] [(get a i) (get b j)])
(while (and (not= nil u) (not= nil v))
(if (compare< u v)
(do
(put c k u)
(++ i)
(set u (get a i)))
(do
(put c k v)
(++ j)
(set v (get b j))))
(++ k))
(when (< k len)
(cond
(not= nil v) (array/blit c a k i)
(not= nil u) (array/blit c b k j)))
c) |
Often torn by these sorts of things because I find Still, I admit to not measuring (^^; |
I think there's a reasonable expectation that core functions (and even "official contrib" functions) are a written approximately as efficiently as possible, i.e. a user likely wouldn't be able to write anything more efficient by hand. If I find that isn't the case, I make a PR about it 😃 |
Great work @primo-ppcg ! |
Was looking at @MikeBeller's janet-benchmarksgame for reasons (TM), and noticed this text:
via https://github.com/MikeBeller/janet-benchmarksgame#ideas-for-improving-janet-performance |
With the merger of #145, I think we have just about everything needed. I've prepared a branch which adds
math/factor
for the purpose of evaluation.Using this test script, I get timings like this:
Which is definitely fast enough to be of use.
One issue that I currently have is that
math/gcd
does not work with abstract types, although it does appear to be written by hand (and not a directmath.h
function), so it could possibly be updated. I also think that thepollard-rho
implementation could be cleaned up a bit.The text was updated successfully, but these errors were encountered: