From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id 88DCA3857C77; Sat, 24 Oct 2020 18:09:13 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 88DCA3857C77 From: "tkoenig at gcc dot gnu.org" To: gcc-bugs@gcc.gnu.org Subject: [Bug rtl-optimization/97459] __uint128_t remainder for division by 3 Date: Sat, 24 Oct 2020 18:09:13 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: rtl-optimization X-Bugzilla-Version: 11.0 X-Bugzilla-Keywords: missed-optimization X-Bugzilla-Severity: normal X-Bugzilla-Who: tkoenig at gcc dot gnu.org X-Bugzilla-Status: UNCONFIRMED X-Bugzilla-Resolution: X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: attachments.created Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 X-BeenThere: gcc-bugs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-bugs mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 24 Oct 2020 18:09:13 -0000 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D97459 --- Comment #11 from Thomas Koenig --- Created attachment 49438 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=3D49438&action=3Dedit Numbers a, b so that 2^b =E2=89=A1 1 mod a up to b=3D64, larger b taken if= several solutions exist Here is the promised table of divisors for which this optimization is possible. For example, the line=20 9 60 means that the remainder of a division by 9 can be calculated by #define MASK60 ((1ul << 60) - 1) unsigned rem_9 (__uint128_t n) { __uint64_t a, b, c; a =3D n & MASK60; b =3D (n >> 60) && MASK60; c =3D (n >> 120); return (a+b+c) % 9; } The number of terms varies; for b=3D64, it is two terms; for 63 >=3D b >=3D 43, it is three terms, and for the rest, it is four terms. 67 is the first odd divisor for which there is no such shortcut, the next one is 83. Those are the only gaps below 100. Of course, if a is in the list, then a*2^n can be treated by shifting (like it was shown for a=3D10). Now, the interesting question, what to make of it.=