From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from tb-mx0.topicbox.com (localhost.local [127.0.0.1]) by tb-mx0.topicbox.com (Postfix) with ESMTP id D9B2FF5DEB6 for <9fans@9fans.net>; Mon, 16 Dec 2019 21:28:44 -0500 (EST) (envelope-from bakul@bitblocks.com) Received: from tb-mx0.topicbox.com (localhost [127.0.0.1]) by tb-mx0.topicbox.com (Authentication Milter) with ESMTP id 8F38CD4C70A; Mon, 16 Dec 2019 21:28:44 -0500 ARC-Seal: i=1; a=rsa-sha256; cv=none; d=topicbox.com; s=arcseal; t= 1576549724; b=aHuHxCMACDCN3ZJs6EX62/0toshrtoeod5l7d8OAKEtM/1iEEx eLQPkMKta8nU6V36mEkt6lTWl03T3iOe4guSj3pIbjth4k3uItTRUwa5cRh0e8+l 3O9NbXcj94QihxVmxzzw9qyUuOWMibNYfcr3Djet2WDJt9sZ4AFTJfQnfAh2UZ5Z iwOfgbYAILtLtAFJ8Uv5LbT5oNZ7YISuODewOEPDGEzWN52Y/NIAAYiYfctatC97 YpW0lU6ST6r48d/pMXGUWCqLU/+x4FBenpnwoqZzBfQAQZoutZxMA2Vd7DW/TmRM mGsLDIhZLd6L2KXAS/2nNUJoXJBiAMSn1ZUA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d= topicbox.com; h=to:subject:in-reply-to:references:from :mime-version:content-type:content-id:content-transfer-encoding :date:message-id; s=arcseal; t=1576549724; bh=FYne6TKjoeQpEOEpYT 0fYl6u0E2esSg40zwwcWbLj8A=; b=I8bJKPJmGNMS0L6AW1f+xER6QEqtKRk9Zi uX8uYzi0UYT2deXqojOfFYxzwVBHPLl5Br+Kg4nuTYebjFjqJxieBuqzLsmd0RF4 yh2xabVnKFLIaTPLOiB5kYzQgGVL9HafypJviaLHHXyG1DIfoCymkKAdX8Zc5k6n 1TEXyD59KSflPzqxldncIm3adnawAdEoFbeFeQUxgt6toK3rWy2DJdUx6nVEwsLb C6zyk9xMLl67bx88a0nO80ef5TNtLqaAYkXKjc8SdbiJjA6IK7xLoqtnQ43pxgjE lJn0aD5RQHYhZBMnzCV/9wVM3pxw/dsB8hRvz0EN84c+K547/s9w== ARC-Authentication-Results: i=1; tb-mx0.topicbox.com; arc=none (no signatures found); dkim=none (no signatures found); dmarc=none policy.published-domain-policy=none policy.applied-disposition=none policy.evaluated-disposition=none (p=none,d=none,d.eval=none) policy.policy-from=p header.from=bitblocks.com; iprev=pass smtp.remote-ip=173.228.5.8 (ns1.bitblocks.com); spf=pass smtp.mailfrom=bakul@bitblocks.com smtp.helo=mail.bitblocks.com; x-aligned-from=pass (Address match); x-ptr=fail smtp.helo=mail.bitblocks.com policy.ptr=ns1.bitblocks.com; x-return-mx=pass header.domain=bitblocks.com policy.is_org=yes (MX Record found); x-return-mx=pass smtp.domain=bitblocks.com policy.is_org=yes (MX Record found); x-vs=clean score=0 state=0 Authentication-Results: tb-mx0.topicbox.com; arc=none (no signatures found); dkim=none (no signatures found); dmarc=none policy.published-domain-policy=none policy.applied-disposition=none policy.evaluated-disposition=none (p=none,d=none,d.eval=none) policy.policy-from=p header.from=bitblocks.com; iprev=pass smtp.remote-ip=173.228.5.8 (ns1.bitblocks.com); spf=pass smtp.mailfrom=bakul@bitblocks.com smtp.helo=mail.bitblocks.com; x-aligned-from=pass (Address match); x-ptr=fail smtp.helo=mail.bitblocks.com policy.ptr=ns1.bitblocks.com; x-return-mx=pass header.domain=bitblocks.com policy.is_org=yes (MX Record found); x-return-mx=pass smtp.domain=bitblocks.com policy.is_org=yes (MX Record found); x-vs=clean score=0 state=0 X-ME-VSCause: gggruggvucftvghtrhhoucdtuddrgedufedrvddtiedggeejucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucenucfjughrpefvufgjfh fhgggtgfesthektddttddtjeenucfhrhhomhepuegrkhhulhcuufhhrghhuceosggrkhhu lhessghithgslhhotghkshdrtghomheqnecukfhppedujeefrddvvdekrdehrdeknecurf grrhgrmhepihhnvghtpedujeefrddvvdekrdehrdekpdhhvghlohepmhgrihhlrdgsihht sghlohgtkhhsrdgtohhmpdhmrghilhhfrhhomhepoegsrghkuhhlsegsihhtsghlohgtkh hsrdgtohhmqecuuffkkgfgpedvfeelieenucevlhhushhtvghrufhiiigvpedt X-ME-VSCategory: clean Received-SPF: pass (bitblocks.com: 173.228.5.8 is authorized to use 'bakul@bitblocks.com' in 'mfrom' identity (mechanism 'ip4:173.228.5.8/29' matched)) receiver=tb-mx0.topicbox.com; identity=mailfrom; envelope-from="bakul@bitblocks.com"; helo=mail.bitblocks.com; client-ip=173.228.5.8 Received: from mail.bitblocks.com (ns1.bitblocks.com [173.228.5.8]) by tb-mx0.topicbox.com (Postfix) with ESMTP for <9fans@9fans.net>; Mon, 16 Dec 2019 21:28:44 -0500 (EST) (envelope-from bakul@bitblocks.com) Received: from bitblocks.com (localhost [127.0.0.1]) by mail.bitblocks.com (Postfix) with ESMTP id 1A4ED156E42D for <9fans@9fans.net>; Mon, 16 Dec 2019 18:28:35 -0800 (PST) To: 9fans <9fans@9fans.net> Subject: Re: [9fans] dc(1) exponent limits In-reply-to: Your message of "Tue, 17 Dec 2019 09:46:52 +1100." References: Comments: In-reply-to Rob Pike message dated "Tue, 17 Dec 2019 09:46:52 +1100." From: Bakul Shah MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-ID: <51786.1576549715.1@bitblocks.com> Content-Transfer-Encoding: 8bit Date: Mon, 16 Dec 2019 18:28:35 -0800 Message-Id: <20191217022843.1A4ED156E42D@mail.bitblocks.com> Topicbox-Policy-Reasoning: allow: sender is a member Topicbox-Message-UUID: f56945bc-2074-11ea-adee-ac33b2d6851d On Tue, 17 Dec 2019 09:46:52 +1100 Rob Pike wrote: > > % ivy > 652342**52342 > 1.85475753442e+304341 > > )cpu > 8.291ms > > (652342**52342)/34232342 > 9.27378767209e+304340/17116171 > > )cpu > 9.217ms > > float _ > 5.41814385477e+304333 On plan9/pi4 I get % ivy (652342**52342)/34232342 9.27378767209e+304340/17116171 )cpu 181.842ms Somewhat surprisingly this is better than on linux/pi4: $ ivy (652342**52342)/34232342 9.27378767209e+304340/17116171 )cpu 247.783ms For comparison, gambit-scheme (on linux) takes 126ms. $ gsi ... > (time (begin (/ (expt 652342 52342) 34232342) #f)) (time (begin (/ (expt 652342 52342) 34232342) #f)) 128 ms real time 126 ms cpu time (116 user, 10 system) 3 collections accounting for 3 ms real time (3 user, 0 system) 545796 bytes allocated 1051 minor faults 1 major fault #f But it doesn't have big floats so exact->inexact conversion returns +inf and takes 15 seconds to do so! > 50 minutes feels excessive; dc seems to work very hard. The excessive slow down is dc using nothing fancier than the grade-school multiplication algorithm that has an O(n^2) complexity. For large numbers Go's math/big package uses the Karatsuba algorithm which has is approx. O(n^1.58). Gambit-Scheme uses the Schönhage–Strassen algorithm for really large numbers (in addition to Karatsuba where it is better) but that doesn't matter much for this computation.