Comments URL: https://news.ycombinator.com/item?id=46923051

Points: 69

# Comments: 22

Comments URL: https://news.ycombinator.com/item?id=45719633

Points: 4

# Comments: 0

Comments URL: https://news.ycombinator.com/item?id=43909032

Points: 3

# Comments: 0

And congratulations on the discovery!

1. I guess the most time consuming part is multiplication, right? What kind of FFT do you use? Schönhage-Strassen, multi-prime NTT, ..? Is it implemented via floating-point numbers or integers?

2. Not sure if you encountered this, but do you have any advice for small mulmod (multiplication reduced by prime modulus)? By small I mean machine-word size (i.e. preferably 64-bits).

3. For larger modulus, what do you use? Is it worth precomputing the inverse by, say, Newton iteration or is it faster to use asymptotically slower algorithms? Do you use Montgomery representation?

4. Does the code use any kind of GCD? What algorithm did you choose?

5. Now this is a bit broad question, but could you perhaps compare the traditional algorithms implemented sequentially (e.g. GMP) and algorithm suitable to run on GPUs? I mean, does it make sense to use, say, a quadratic algorithm amenable to parallel execution, rather than a asymptotically faster (and sequential) algorithm?

Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1

https://arxiv.org/abs/1602.02830

Ternary Neural Networks for Resource-Efficient AI Applications

https://arxiv.org/abs/1609.00222

I'm curious, can you give some examples what kind of bugs did you discover?

The Genuine Sieve of Eratosthenes https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Could you be more specific? I think for that to work one would also need the upper half of 64x64 multiplication and `vpmullq` provides only the lower half. You could break one 64x64 multiplication into four 32x32 multiplications (i.e. emulate the full 64x64 = 128 bits multiplication) but I was under the impression that this was slow.

Comments URL: https://news.ycombinator.com/item?id=30151367

Points: 1

# Comments: 0

Comments URL: https://news.ycombinator.com/item?id=29420622

Points: 310

# Comments: 348

thanks for very interesting article, again!

Do you think the very fast division on M1 has any implications for 128/64 narrowing division as well? Do you know of a faster way than the method by Moller and Granlund? Do you plan on to include 128/64 division in libdivide?

And I asked this question before but the parent post got flagged so I'm trying once more: at the very bottom of the Labor of Division (Episode V) post [1], is it really possible for the second `qhat` (i.e. `q0`) to be off by 2? Do you have any examples of that?

[1] https://ridiculousfish.com/blog/posts/labor-of-division-epis...

An op unlovely as division

An op whose answer must be guessed

And then, through multiply, assessed;

An op for which we dearly pay,

In cycles wasted every day.

Division code is often hairy;

Long division's downright scary.

The proofs can overtax your brain,

The ceiling and floor may drive you insane.

Good code to divide takes a Knuthian hero

But even God can't divide by zero!

-- Henry S. Warren Jr.

Hacker's Delight