These are chat archives for bluescarni/piranha

14th
Jan 2016
Francesco Biscani
@bluescarni
Jan 14 2016 00:08
@isuruf I left a couple of comments on the PR. I am not sure what the best way of proceeding here is, it seems like we are playing whack-a-mole with special cases
we smash one, another one pops up
I am wondering if it might be better to cast everything to dlimb_t and do the shifting there... but I don't like this a lot as I'd prefer to limit the use of the dlimb_t type as much as possible
as it's the type which is not available on MSVC 64 bit
Francesco Biscani
@bluescarni
Jan 14 2016 00:16
Just thinking aloud: how about organising the code so that you start ironing out the special cases from top to bottom
something like this maybe:
  • if n == 0u or this is zero, nothing to do, return success;
  • if n >= limb_bits * 2u, return failure;
Francesco Biscani
@bluescarni
Jan 14 2016 00:23
This message was deleted
(mhm maybe it would make sense to have a helper method that takes in input a limb_t and a shift size, and returns the shifted limb plus the digits that spilled over from the shift?)
This message was deleted
Francesco Biscani
@bluescarni
Jan 14 2016 00:37
  • then maybe you could use it on both lo and hi separately, first shift hi and then, assuming there's nothing spilling, shift lo and add to hi the spill from lo?
After all we know already we need to deal only with 2 limbs, so if there's spilling from hi it's a failure, otherwise we are good?
Francesco Biscani
@bluescarni
Jan 14 2016 10:38
@isuruf sorry if it reads a bit rambling, just throwing ideas :)
@certik I am in the process of changing the license, I should be done tonight or tomorrow. I just copied verbatim the approach of GMP for licensing
Isuru Fernando
@isuruf
Jan 14 2016 13:56
@bluescarni, your suggestion about ironing out the special case is good.
Having a helper method wouldn't make much of a difference to the code as in that case also, we have to look at several cases
Francesco Biscani
@bluescarni
Jan 14 2016 16:27
@isuruf fair enough, I guess my main point is that it might be worth to perform first the shift of hi and then lo
since an excessive shift of hi is ultimately the condition that leads to failure
obviously everything needs to be done in local variables and committed to the member hi and lo only at the end, when it is certain that no errors are possible anymore
in order to avoid leaving the class in a mixed state
Isuru Fernando
@isuruf
Jan 14 2016 16:32
Right. You mean instead of looking at several cases of n look at hi first? That's a good idea
Francesco Biscani
@bluescarni
Jan 14 2016 16:33
That would be the idea yes... after all, if hi is shiftable without overflow the operation cannot fail can it?
Isuru Fernando
@isuruf
Jan 14 2016 16:34
It can actually. for example 2**31 << 34 is not possible whereas 1 << 34 is possible
Francesco Biscani
@bluescarni
Jan 14 2016 16:36
ok so the hi shift can succeed but lo can still fail
damnit
Isuru Fernando
@isuruf
Jan 14 2016 16:38
Although that case can be converted by replacing hi with lo and doing the operation n - limb_bits
Francesco Biscani
@bluescarni
Jan 14 2016 16:39
right... I have the feeling that I'd rather have the failure modes handled all together at the beginning, but I don't know if this is efficient
I need to drive home now, but I'll be online later... need to think about this more :) nasty little bugger
Isuru Fernando
@isuruf
Jan 14 2016 16:45
if (n == 0u) return 0;
if (m_limbs[0u] == 0u && m_limbs[1u] == 0u) return 0;
if (n >= 2u * limb_bits) return 1;
if (n >= limb_bits) {
    if (m_limbs[1u] != 0u) return 1;
    hi = m_limbs[0u];
    lo = 0u;
    n -= limb_bits;
} else {
    hi = m_limbs[1u];
    lo = m_limbs[0u];
}

if (m_limbs[1u] >= (limb_t(1) << (limb_bits - n))) return 1;
lo = lo << n;
hi = (hi << n) + (lo >> limb_bits - n);
Something like this?
Okay. will talk to you later
Francesco Biscani
@bluescarni
Jan 14 2016 22:00
I like the logic of this version much better :) Two lines above the last one, should that be if (hi >= ... rather than if (m_limbs[1u] >=?
Also I think there is still the risk of shifting too much, in that same line? I mean, if n == 0
Francesco Biscani
@bluescarni
Jan 14 2016 22:07
This message was deleted
Francesco Biscani
@bluescarni
Jan 14 2016 22:17
I think you should also switch the last two lines right? Otherwise in the (currently) last line you are right-shifting the lo that you just left-shifted in the previous line
Francesco Biscani
@bluescarni
Jan 14 2016 22:23
I was thinking that maybe all these issue with n == 0 (note also the excessive right shift on the last line) can go away if we add another special casing on top:
if (n == limb_bits) {
    m_limbs[1u] =  m_limbs[0u];
    m_limbs[0u] = 0u;
    return 0;
}
This message was deleted