Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.arch Subject: Re: endian history Date: Fri, 18 Sep 2026 15:36:15 -0700 Organization: A noiseless patient Spider Lines: 93 Message-ID: <86ik42tcf4.fsf@linuxsc.com> References: <10uks4f$1dqo$1@gal.iecc.com> <10vnjp6$1df4$1@gal.iecc.com> <10vns1f$3a252$1@dont-email.me> <10vpblp$3mkd1$1@dont-email.me> <10vphh0$3o9jl$1@dont-email.me> <117gj6t$1b95v$2@dont-email.me> <6a9c1c93.39172234@news.eternal-september.org> <117j3es$24qgq$6@dont-email.me> <117n6ho$35j69$1@paganini.bofh.team> <6a9f7664.1891062@news.eternal-september.org> <2026Sep8.125659@mips.complang.tuwien.ac.at> <117pnpg$f179$2@dont-email.me> <11898n9$1nc06$2@dont-email.me> <118d6ld$1tkm9$1@paganini.bofh.team> <118dl5f$37cfv$1@dont-email.me> <118e8kg$3f05h$1@dont-email.me> <868q4zuhz4.fsf@linuxsc.com> <118jitv$1cm6b$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Fri, 18 Sep 2026 22:36:20 +0000 (UTC) Injection-Info: dont-email.me; logging-data="1824205"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+IDz1QOPXZP5jBHuw28a1rKo7ke8iWrH8="; posting-host="742ba13f59dd80260e7d5d77f8995b11" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:xAnGrUgFWiJcDCLHRFPMk6m6bxs= sha1:2dFPIs7ZuNYThjiHkwqGgtdvqkA= sha256:Gzlh4X9WIdZqLEKsN7WC7+u42OL51h35QaVBiXrtGDk= sha1:LXB82WeTAKUmIjafqSjqI/Trtsc= sha256:U6D1phLij/uJp5HCgLNoUFP+kdJSgQ0H4ixwKDbHhyI= Xref: csiph.com comp.arch:118093 Terje Mathisen writes: > Tim Rentsch wrote: > >> Terje Mathisen writes: >> >> [...] >> >>> There was an Advent of Code puzzle in 2022 (last day) where you had to >>> work in symmetrical base-5, using '-' and '=' for -1 and -2, along >>> with '0', '1', '2'. >>> >>> You had to parse 113 such numbers, all happened to be positive, but >>> they did of course not need to be. With symmetrical encoding, there is >>> no extra minus sign in front, just a negative first digit. >>> >>> The fast solutions did each input line/number in about 4-5 us, then >>> you had to return the (decimal) sum, before converting that back to >>> the same base-5 system. >> >> I'm wondering why a seemingly simple problem took as much time as >> this. Maybe I'm misunderstanding the problem statement. Is there >> one (base negative 5) input number per line? Surely converting such >> an input to binary can be done more quickly than 4 microseconds. > > Oops! > > I meant 4-5 ns not microseconds. > > 3 orders of magnitude does make a small difference... Just a little... :) >>> Just like decimal, it is a lot easier to convert ascii to binary than >>> binary to ascii, the difference between div/mod every digit and a >>> single mul. >> >> Now I'm curious to see how you implemented the binary-to-ascii part >> of the problem. Do you still have the code around? > > Sure: > > const BASE:i64 = 5; > const VALUE:[i8;256] = [ > 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, > 0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,1,2,0,0,0,0,0,0,0,0,0,0,-2,0,0, > 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, > 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, > 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, > 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, > 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, > 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]; > > const DIGITS:[u8;5] = [b'0',b'1',b'2',b'=',b'-']; > > fn tobase(n:i64) -> String > { > let mut n = n; > let mut buf:[u8;32] = [0;32]; > let mut p = buf.len(); > loop { > let r = n % BASE; // positive remainder for positive $BASE > let d = DIGITS[r as usize]; > n = (n-VALUE[d as usize] as i64) / BASE; // Exact division! > p -= 1; > buf[p] = d; > if n == 0 {break;} > } > std::str::from_utf8(&buf[p..buf.len()]).unwrap().to_string() > } I'm guessing this code is in Rust. Can I ask you to translate it to C for me? Mostly I can guess at the meaning, but as I am only a novice with Rust I worry that my guessing would be wrong in some cases, and wrong functionality would result. > In order to be really fast, the compiler has to recognize that both > the div and mod should use reciprocal mul (standard), and if possible, > only do it once. > ... > Checking Godbolt: > > Turns out it is actually generating two IMULs, but it should work for > both positive and negative inputs... I suspect the two multiplys are a consequence of the usual way for producing a quotient and remainder: quotient = n / BASE; remainder = n - quotient*BASE So one of the multiplys is doing a divide by BASE, and the other multiply is doing a multiply by BASE. That is plausible anyway.