last day (19 days later) » 

16:27
1
Q: How to combine elements in Karatsuba multiplication

tansyI'm trying to implement multiplication using the Karatsuba algorithm. The usual bit masking and shifting approach implemented in mul_kar2() works. In mul_kar2_au(), I'm struggling with combining the individual components into a "single number" using a union, but can be an array. When I combine th...

Your program is in C, not C++. Please tag the actual language you are using.
Your opening paragraph is a tough read, but it might be not that relevant to your question. Instead of showing the "Karatsuba algorythm", show the calculation that fails. For example, before assigning values to aru64.au16[i], make sure they are what you expect. If z0, z1, m_2, and z2 are not what you expect, then backtrack through the calculation. If they are, then skip the earlier calculation and simply assign the expected values, as in aru64.au16[0] = 4891;, and focus on how you get the full value out of aru64 (which probably depends on the language, so check the tags).
Side note, in C++ don't use unions use std::variant. I also would remove all your typedefs. Just type std::uint32_t where you need it. But yes probably you should remove the "C++" tag
Check the size needed to compute and store z1.
(Karatsuba did not just suggest to use three multiplications of smaller numbers to compute a product of large factors: The pivotal idea is to use this recursively.)
BTW arm64 can construct both the lower 64 bits and upper 64 bits of the product of two 64-bit integers trivially (each in one instruction)
16:27
(I also would remove all your typedefs. Just type std::uint32_t where you need it) @PepijnKramer: I used u32/u64 for brevity and clarity. Last thing I want is to be ignored because of "to much code to read"
Multiplying u32 values like in (ha + la) * (hb + lb) may lead to u64 values...
@greybeard: it doesnt have to be recursive here as cutting used bits in hall is enough to fit in processor word.
(make sure they are what you expect) @JaMiT: they are. If I use commented line instead, it works. But it requires casting to wider integer that I don't want to use.
(@Jean-BaptisteYunès ha + la and hb + lb are (potentially) 17-bit values, but yes, their product is a bit much for 32 bits.)
It does have to be recursive to be "true" Karatsuba multiplication. To implement double, even quadruple length products, using long multiplication is simpler and faster.
(It does have to be recursive to be "true" Karatsuba multiplication) @greybeard: when you fit in desired word width, you don't have to divide further; I will check long multiplication add you suggest.
@tansy Adding defines just to reduce a bit of typing is the wrong kind of optimization I am afraid. All C++ programmers will know what std::uint32_t is and no one will know what u32 is without looking up your typedef. So it might be breef and clear for you (now) it will not be for others (and your future self). Just know writing the least amount of characters in your source is NOT an optimization goal.
16:27
@PepijnKramer: ok, used standard int types.
(arm64 can construct ... product of two 64-bit integers trivially, in one instruction) @harold: where does it say it, cause I can see something different: ARM multiply instructions.
@tansy Arm® A64 Instruction Set Architecture (Armv8-A architecture profile), lists umulh and smulh. But since you're looking at something else, maybe that's not available on the kind of ARM processor that you meant.
@harold: you say it does say this, it does say that... I try to find it and find nothing. I tried to compile multiplication with GCC and it says, the is no __int128 for this target. Therefore I have to 'cast' it somehow onto bigger 'target' (I mean bigger int). Only comprehensive list of assembler instructions doesn't have umulh, nor anything like that, and MUL, alias MADD, only produces lower bits of product.
@tansy you didn't target 64-bit ARM, that list does have umulh in it (but as {U|S}MULH so ctrl+F is defeated) and here's the official page E: and here's umulh being used by clang
@harold: I hope you understand that I have to do it in C (C++) and standard C compiler has to do it. >so ctrl+F is defeated)< well, "UMULH" is not "{U|S}MULH". So you're almost right.
@tansy "{U|S}MULH" means both "UMULH" and "SMULH" it's just a shortened notation, idk what you mean by standard C compiler but if you don't like the clang example well here's gcc using umulh as well
16:27
>"{U|S}MULH" means both "UMULH" and "SMULH"< yeah, great. Note, go to that site, press Ctrl+F, and find 'UMULH'. Good luck.
I know, I acknowledged that already.
> well here's gcc using umulh as well < @harold: how dif you manage to compile it, white I got failed due to lack of `__int128'?
@tansy "they are." -- Good, then you know which piece of advice is applicable. -- "If I use commented line instead, it works." -- That's not the piece of advice I gave. I wrote "skip the earlier calculation and simply assign the expected values, as in aru64.au16[0] = 4891;". Don't show us "the Karatsuba algorithm". Show us just "only the last (least significant) 16 bits are correct." Given your assertion, a minimal example should have a function with five lines of code: four assignments to elements of aru64.au16 and a return (plus a main function to produce output).
> and hb + lb are (potentially) 17-bit values, but yes, their product is a bit much for 32 bits < @greybeard: that made me realize that, unless there is way to do this multiplication with carry carried over, It would require another iteration of algorithm, which makes it uneconomical against long multiplication, that can fit in smaller word/register.
@tansy the difference between when I compiled the code and when you did it is that I compiled for ARM64 and you compiled for ARM but not 64-bit, so native 64-bit operations were not available

  last day (19 days later) »