Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #127055

Re: Catching overflow

From David Brown <david.brown@hesbynett.no>
Newsgroups comp.lang.c
Subject Re: Catching overflow
Date 2018-02-26 00:32 +0100
Organization A noiseless patient Spider
Message-ID <p6vh3a$5mt$1@dont-email.me> (permalink)
References <p6vf4p$ot1$1@dont-email.me>

Show all headers | View raw

On 25/02/18 23:59, jacobnavia wrote:
> I want to do the computation of catalan numbers in 480 bits (my qfloat 
> extension to C)
> 
> But I would like to do as much calculations in 128 bits only (at the 
> start of the series) as possible.
> 
> Possible means until before the computation overflows.
> 
> How can I know if a multiplication will overflow in 128 bits?
> 
> Let's see:
> 
> I want to know when
> 
>      A x B > pow(2,128)
> 
> (A and B < pow(2,64), unsigned long long data)
> 
> If I take logarithms (base 2)
> 
>      log(A) + log(B) > 128*log2
>      log(A) + log(B) > 88.7228
> 
> But log(A) using base 2 is just the rank of the first non-zero bit, for 
> instance:
> log(64) / log(2) --> 6, 64 has the sixth bit 1.
> 
> log(65) / log(2) --> 6.022, so floor(log(65)/log(2)) stil gives me the 
> first 1 bit: bit 6, since 65 is 1000001. And this holds until 127, since
> 
> log(127)/log(2) --> 6.988 127 is 1111111, the first 1 position doesn't 
> change.
> 
> So I conclude that (assuming a function that searches the first non-zero 
> bit called "bsr") the test should be:
> 
>      if ((64 - bsr(A))  + (64 - bsr(B))) > 88)
>          break;
> 
> The "bsr" function is just a single asm instruction in ARM64 (and also 
> in the x86). That would be a very efficient test.
> 
> Do I have a bug somewhere?
> 
> Thanks in advance for your review.

You are close - but it is even easier than you think.  log(pow(2, 128)) 
is just 128, not 88.  I don't know the "bsr" instruction - check that it 
is going in the right direction (MSB or LSB first).

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-25 23:59 +0100
  Re: Catching overflow David Brown <david.brown@hesbynett.no> - 2018-02-26 00:32 +0100
    Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-26 01:45 +0100
  Re: Catching overflow Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-26 00:35 +0000
    Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-26 01:44 +0100
      Re: Catching overflow Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-26 01:25 +0000
        Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-26 10:53 +0100
          Re: Catching overflow Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-26 15:21 +0000
            Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-26 18:36 +0100
              Re: Catching overflow Ike Naar <ike@iceland.freeshell.org> - 2018-02-26 22:55 +0000
                Re: Catching overflow Tim Rentsch <txr@alumni.caltech.edu> - 2018-02-26 21:59 -0800
                Re: Catching overflow David Brown <david.brown@hesbynett.no> - 2018-02-27 09:30 +0100
                Re: Catching overflow Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-03 02:17 -0800
                Re: Catching overflow Steven Petruzzellis <frelwizzen@gmail.com> - 2018-03-03 03:19 -0800
                Re: Catching overflow asetofsymbols@gmail.com - 2018-03-03 03:20 -0800
                Re: Catching overflow Steven Petruzzellis <frelwizzen@gmail.com> - 2018-03-03 03:50 -0800
                Re: Catching overflow David Brown <david.brown@hesbynett.no> - 2018-03-04 13:48 +0100
                Re: Catching overflow asetofsymbols@gmail.com - 2018-03-04 07:11 -0800
                Re: Catching overflow Ike Naar <ike@iceland.freeshell.org> - 2018-03-11 09:21 +0000
                Re: Catching overflow Ike Naar <ike@iceland.freeshell.org> - 2018-03-11 09:26 +0000
                Re: Catching overflow Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-26 22:36 -0700
                Re: Catching overflow David Brown <david.brown@hesbynett.no> - 2018-03-27 15:15 +0200
                Re: Catching overflow Steven Petruzzellis <frelwizzen@gmail.com> - 2018-03-27 06:26 -0700
              Re: Catching overflow Ike Naar <ike@iceland.freeshell.org> - 2018-02-27 19:41 +0000
                Re: Catching overflow Ike Naar <ike@iceland.freeshell.org> - 2018-02-27 20:14 +0000
                Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-27 22:03 +0100
            Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-26 18:40 +0100
              Re: Catching overflow Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-26 18:31 +0000
      Re: Catching overflow Steve Carroll <frelwizzen@gmail.com> - 2018-03-01 08:45 -0800
  Re: Catching overflow bartc <bc@freeuk.com> - 2018-02-26 01:12 +0000
    Re: Catching overflow Richard Damon <Richard@Damon-Family.org> - 2018-02-25 23:10 -0500
  Catching overflow asetofsymbols@gmail.com - 2018-02-25 22:09 -0800
  Catching overflow asetofsymbols@gmail.com - 2018-02-25 23:30 -0800
    Catching overflow asetofsymbols@gmail.com - 2018-02-25 23:31 -0800
    Catching overflow asetofsymbols@gmail.com - 2018-02-28 00:03 -0800
      Catching overflow asetofsymbols@gmail.com - 2018-02-28 22:49 -0800
  Re: Catching overflow "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2018-02-26 23:37 +0800
    Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-26 18:33 +0100
      Re: Catching overflow "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2018-02-28 22:31 +0800
        Re: Catching overflow "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2018-02-28 22:33 +0800
      Re: Catching overflow already5chosen@yahoo.com - 2018-03-01 02:31 -0800
        Re: Catching overflow asetofsymbols@gmail.com - 2018-03-01 05:45 -0800
          Re: Catching overflow already5chosen@yahoo.com - 2018-03-01 08:24 -0800
            Re: Catching overflow asetofsymbols@gmail.com - 2018-03-01 09:03 -0800
              Re: Catching overflow Steve Carroll <frelwizzen@gmail.com> - 2018-03-01 09:32 -0800
            Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-03-01 19:47 +0100
              Re: Catching overflow already5chosen@yahoo.com - 2018-03-01 10:58 -0800
                Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-03-01 20:08 +0100
                Re: Catching overflow already5chosen@yahoo.com - 2018-03-01 11:14 -0800
                Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-03-01 20:50 +0100
                Re: Catching overflow already5chosen@yahoo.com - 2018-03-01 12:18 -0800
            Re: Catching overflow supercat@casperkitty.com - 2018-03-03 15:08 -0800
  Re: Catching overflow jladasky@itu.edu - 2018-02-26 13:07 -0800
    Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-26 22:44 +0100

csiph-web