Re: [go-nuts] Any interest in nat.mulRange simplification/optimization?
Thanks for the tip. A fairly straightforward implementation of this
algorithm gives me about a factor of two speedup for pretty much any value.
I went up to 1e8!, which took about half an hour compared to nearly an hour
for MulRange.
I'll probably stick in ivy after a little more tuning. I may even try
parallelization.
-rob
On Tue, Jan 9, 2024 at 4:54 PM Bakul Shah wrote:
> For that you may wish to explore Peter Luschny's "prime swing" factorial
> algorithm and variations!
> https://oeis.org/A000142/a000142.pdf
>
> And implementations in various languages including go:
> https://github.com/PeterLuschny/Fast-Factorial-Functions
>
> On Jan 8, 2024, at 9:22 PM, Rob Pike wrote:
>
> Here's an example where it's the bottleneck: ivy factorial
>
>
> !1e7
> 1.20242340052e+65657059
>
> )cpu
> 1m10s (1m10s user, 167.330ms sys)
>
>
> -rob
>
>
> On Tue, Jan 9, 2024 at 2:21 PM Bakul Shah wrote:
>
>> Perhaps you were thinking of this?
>>
>> At iteration number k, the value xk contains O(klog(k)) digits, thus the
>> computation of xk+1 = kxk has cost O(klog(k)). Finally, the total cost
>> with this basic approach is O(2log(2)+¼+n log(n)) = O(n2log(n)).
>>
>> A better approach is the *binary splitting* : it just consists in
>> recursively cutting the product of m consecutive integers in half. It leads
>> to better results when products on large integers are performed with a fast
>> method.
>>
>> http://numbers.computation.free.fr/Constants/Algorithms/splitting.html
>>
>>
>> I think you can do recursive splitting without using function recursion
>> by allocating N/2 array (where b = a+N-1) and iterating over it; each time
>> the array "shrinks" by half. A "cleverer" algorithm would allocate an array
>> of *words* of a bignum, as you know that the upper limit on size is N*64
>> (for 64 bit numbers) so you can just reuse the same space for each outer
>> iteration (N/2 multiplie, N/4 ...) and apply Karatsuba 2nd outer iteration
>> onwards. Not sure if this is easy in Go.
>>
>> On Jan 8, 2024, at 11:47 AM, Robert Griesemer wrote:
>>
>> Hello John;
>>
>> Thanks for your interest in this code.
>>
>> In a (long past) implementation of the factorial function, I noticed that
>> computing a * (a+1) * (a+2) * ... (b-1) * b was much faster when computed
>> in a recursive fashion than when computed iteratively: the reason (I
>> believed) was that the iterative approach seemed to produce a lot more
>> "internal fragmentation", that is medium-size intermediate results where
>> the most significant word (or "limb" as is the term in other
>> implementations) is only marginally used, resulting in more work than
>> necessary if those words were fully used.
>>
>> I never fully investigated, it was enough at the time that the recursive
>> approach was much faster. In retrospect, I don't quite believe my own
>> theory. Also, that implementation didn't have Karatsuba multiplication, it
>> just used grade-school multiplication.
>>
>> Since a, b are uint64 values (words), this could probably be implemented
>> in terms of mulAddVWW directly, with a suitable initial allocation for the
>> result - ideally this should just need one allocation (not sure how close
>> we can get to the right size). That would cut down the allocations
>> massively.
>>
>> In a next step, one should benchmark the implementation again.
>>
>> But at the very least, the overflow bug should be fixed, thanks for
>> finding it! I will send out a CL to fix that today.
>>
>> Thanks,
>> - gri
>>
>>
>>
>> On Sun, Jan 7, 2024 at 4:47 AM John Jannotti wrote:
>>
>>> Actually, both implementations have bugs!
>>>
>>> The recursive implementation ends with:
>>> ```
>>> m := (a + b) / 2
>>> return z.mul(nat(nil).mulRange(a, m), nat(nil).mulRange(m+1, b))
>>> ```
>>>
>>> That's a bug whenever `(a+b)` overflows, making `m` small.
>>> FIX: `m := a + (b-a)/2`
>>>
>>> My iterative implementation went into an infinite loop here:
>>> `for m := a + 1; m <= b; m++ {`
>>> if b is `math.MaxUint64`
>>> FIX: add `&& m > a` to the exit condition is an easy fix, but pays a
>>> small penalty for the vast majority of calls that don't have b=MaxUint64
>>>
>>> I would add these to `mulRangesN` of the unit test:
>>> ```
>>> {math.MaxUint64 - 3, math.MaxUint64 - 1,
>>> "6277101735386680760773248120919220245411599323494568951784"},
>>> {math.MaxUint64 - 3, math.MaxUint64,
>>> "115792089237316195360799967654821100226821973275796746098729803619699194331160"}
>>> ```
>>>
>>> On Sun, Jan 7, 2024 at 6:34 AM John Jannotti wrote:
>>>
I'm equally curious.
FWIW, I realized the loop should perhaps be
```
mb := nat(nil).setUint64(b) // ensure mb starts big enough for b, even
on 32-bit arch
for m := a + 1; m <= b; m++ {
mb.setUint64(m)
z = z.mul(z, mb)
}
```
to avoid allocating repeatedly for `m`, which yields:
BenchmarkIterativeMulRangeN-10 354685 3032 ns/op2129 B/op
48 allocs/op
On Sun, Jan 7, 2024 at 2:41 AM
Re: [go-nuts] How could we emulate condition variables using Go channels only?
> Something like this? https://go.dev/play/p/_H3kFjprAGG No, sorry. The goal is to emulate a full monitor just with channels, as demonstrated in the referenced text (see the Stack example). The Mutex is likely correct, but the Signal has yet to pass the scrutinity of the folks here. -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/8f85e31d-103c-4138-a4a6-e7e56f871bc3n%40googlegroups.com.
Re: [go-nuts] How could we emulate condition variables using Go channels only?
On Fri, Jan 12, 2024 at 7:57 PM Rochus Keller wrote: > Here is the full question with examples (though meanwhile closed as usual in > recent times on stackoverflow, so answer here please): > https://stackoverflow.com/questions/77802102/mutex-and-condition-variables-in-go-without-using-the-sync-package > > This is a conceptual question based on the duality of monitors and message > passing. My goal is to see and be able to experiment with a correct and > complete example of a mutex with condition variables in Go which only use Go > channels for implementation, as a proof of concept. Only then we can discuss > how far it makes sense from an engineering standpoint. > Something like this? https://go.dev/play/p/_H3kFjprAGG -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAA40n-UWgi%3D8OvAvs1gR3kudxxQFNfnFgDNLb3OUq-8iLAGrXw%40mail.gmail.com.
[go-nuts] How could we emulate condition variables using Go channels only?
Here is the full question with examples (though meanwhile closed as usual in recent times on stackoverflow, so answer here please): https://stackoverflow.com/questions/77802102/mutex-and-condition-variables-in-go-without-using-the-sync-package This is a conceptual question based on the duality of monitors and message passing. My goal is to see and be able to experiment with a correct and complete example of a mutex with condition variables in Go which only use Go channels for implementation, as a proof of concept. Only then we can discuss how far it makes sense from an engineering standpoint. -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/e31ddd07-8e08-4cce-8232-210534ef1515n%40googlegroups.com.
Re: [go-nuts] Re: Rendering fonts in Go
On Fri, Jan 12, 2024 at 12:34 PM 'Brian Candler' via golang-nuts wrote: > At worst, it may possible to compile C into Go. It sounds mad, but I believe > SQLite has been ported to pure Go this way. Challenge accepted: https://pkg.go.dev/modernc.org/libfreetype -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAA40n-URgHjw%3DarU1NZAo9XfQ%3DJ0qDwMiFZHPE-94NDuhQx%2B%2Bw%40mail.gmail.com.
[go-nuts] pauseEnd times in runtime.Memstats
In runtime.Memstates, one of the stats given is the timestamps for the last 256 garbage collections in the PauseEnd array, i.e. when those garbage collections took place. So if you subtract one timestamp from another, you can find out how much time took place between garbage collections. Is there anything else that you do with PauseEnd times? -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/54b9e68c-942c-40d4-8373-5e9a8bfc5cbdn%40googlegroups.com.
[go-nuts] Re: Rendering fonts in Go
At worst, it may possible to compile C into Go. It sounds mad, but I believe SQLite has been ported to pure Go this way. https://pkg.go.dev/modernc.org/sqlite https://twitter.com/bradfitz/status/855271867162083329?lang=en https://groups.google.com/g/golang-nuts/c/QDEczMhlQBU/m/4lCn2kP0AwAJ https://github.com/elliotchance/c2go On Thursday 11 January 2024 at 22:05:56 UTC Yuliana Zigangirova wrote: > Thank you, I will have a look. I have hoped on finding pure Go, > but may be it is unrealistic. > > On Saturday, December 23, 2023 at 1:10:13 AM UTC+3 Howard C. Shaw III > wrote: > >> I think Freetype may still be your best bet - but rather than the >> Freetype port, you would need to use a wrapper that calls the Freetype C >> library, such as https://github.com/danielgatis/go-freetype >> >> -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/a81de428-ce73-4a80-ae3e-ed516e01b206n%40googlegroups.com.
