Timeline for Do there exist fast multiplication algorithms for two integers with one of them being static?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 18, 2020 at 16:03 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jul 21, 2020 at 16:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jun 21, 2020 at 15:30 | answer | added | JEK | timeline score: 1 | |
| Jun 21, 2020 at 9:13 | comment | added | gnasher729 | The proportion of n-bit integers with log n odd numbers in their Collatz sequence is ridiculously small. For n=1024 about 2^100/10! That is one in 2^924 * 10! | |
| Jun 21, 2020 at 4:46 | history | edited | John Flemin | CC BY-SA 4.0 |
added 260 characters in body
|
| Jun 21, 2020 at 4:41 | history | edited | John Flemin | CC BY-SA 4.0 |
added 260 characters in body
|
| Jun 21, 2020 at 2:55 | comment | added | njuffa | It would improve the question if that background information would be edited into it, as comments on this site are rather ephemeral and not everybody reads comments. | |
| Jun 21, 2020 at 1:10 | comment | added | John Flemin | Actually, I got the idea from a recent paper that utilizes the Collatz conjecture to do multiplication, it can be extremely efficient for some integers and through bruteforce I imagine any arbitrary integer could be broken down to one that satisfies the requirement and a remainder. But hopefully its not the only algorithm of its kind? sci-hub.tw/10.1007/s00224-020-09986-5 GMP C code: fit.vutbr.cz/~ibarina/tmp/n.c (it does beat GMP for these types of integers, ones that have short collatz trajectories) | |
| Jun 21, 2020 at 1:07 | comment | added | John Flemin | I have not been able to find anything, my last statement is a conjecture. And there is no structure to rely on in either operand, both are arbitrary. I conjectured that there may be some algorithm involving a tradeoff - algorithm that does analysis of the operand that is held static. And it simply doesn't make sense to do it for an integer that is never seen again. | |
| Jun 21, 2020 at 0:30 | comment | added | njuffa | Could you state where have you looked for potential answers so far (this avoids duplication of effort)? Do these piece-wise constant factors have any particular structure, e.g. very few 1-bits? In general, any multiplication method that uses recoding of the operands should be able to benefit from reduced work when one of the operands is constant, e.g. Booth-encoding for hardware multipliers, or FFT prep work in FFT-based software multiplication. Neither of these examples would seem to apply to operands of length 1024 bits, though. | |
| Jun 20, 2020 at 23:07 | review | First posts | |||
| Jun 22, 2020 at 3:44 | |||||
| Jun 20, 2020 at 23:03 | history | asked | John Flemin | CC BY-SA 4.0 |