From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from tb-mx1.topicbox.com (localhost.local [127.0.0.1]) by tb-mx1.topicbox.com (Postfix) with ESMTP id 26D0AE273C7 for <9fans@9fans.net>; Mon, 16 Dec 2019 21:53:53 -0500 (EST) (envelope-from bakul@bitblocks.com) Received: from tb-mx1.topicbox.com (localhost [127.0.0.1]) by tb-mx1.topicbox.com (Authentication Milter) with ESMTP id A9EC5FFEC7F; Mon, 16 Dec 2019 21:53:53 -0500 ARC-Seal: i=1; a=rsa-sha256; cv=none; d=topicbox.com; s=arcseal; t= 1576551233; b=MQCD5lTw5H3CPG3TukNIsrQZWGxzMXrCVUuGD7Qh5YQQdswdLB o28e8OzAUbhiZ/+ORUoGD6xiDcC/+294fLTvkeLN16pWT3GYmxM3q+8B1vXVirZA wSCB1is/VaSiTFV3cfSqgAizxXGlkp7K0vM6sLTiph3YpQyuBxcIjDK/g8vT9Ubd TlUkfEk/qD/+Re3lw3kNXSIpxJVJe3VJW1tpZmIPkIxwdNxdR+bm158YHj/dzLyk A5EEN3kx/XcC7wHVWExfNkmAwgPIglqJdA7Kp2iUJu76RxkpBBdg+/4BNKGAUb2b BcoHibP1IMQ8peZR37JbujvqOCaU8De8XSog== 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=1576551233; bh=Sisk962bN4vARa/HBp qZWDmDupwAdIRWeD9IR4F/BSI=; b=wwvnsHZAphmIZRB3wUDp+yBohYyDYFGGVR DNttjb3epQv8HsDHQalsygdV2MNk4KmARYDMMqPptcgq5Jvsiu4zFZc2emVz8/F1 iG7wWBdyQCgTX1N1tKBFE60NDC7RJRBaoSSVZglKCG8RbJyvKW68NVYTZ1cYeLSg Grlf+Z6tGozisVk9NUzXaPz1GVhZw9c1VOW3l2R1vSJTEN+NFOlTWL8lR7c4u2Di eMa5CNaS4ns0ApOdO/WiCwLDVuxJIhEo6U1Jaa6sFxsSa7XEwJ6TdGcPUxaPILj8 q9thxnAJJC3o9tw7yG4uBgQsZDOG61BfbDudkYSN/lwWcGMqpirA== ARC-Authentication-Results: i=1; tb-mx1.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-mx1.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: gggruggvucftvghtrhhoucdtuddrgedufedrvddtiedgheefucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucenucfjughrpefvufgjfh fhgggtgfesthektddttddtjeenucfhrhhomhepuegrkhhulhcuufhhrghhuceosggrkhhu lhessghithgslhhotghkshdrtghomheqnecukfhppedujeefrddvvdekrdehrdeknecurf grrhgrmhepihhnvghtpedujeefrddvvdekrdehrdekpdhhvghlohepmhgrihhlrdgsihht sghlohgtkhhsrdgtohhmpdhmrghilhhfrhhomhepoegsrghkuhhlsegsihhtsghlohgtkh hsrdgtohhmqecuuffkkgfgpedvkeekleenucevlhhushhtvghrufhiiigvpedt 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-mx1.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-mx1.topicbox.com (Postfix) with ESMTP for <9fans@9fans.net>; Mon, 16 Dec 2019 21:53:52 -0500 (EST) (envelope-from bakul@bitblocks.com) Received: from bitblocks.com (localhost [127.0.0.1]) by mail.bitblocks.com (Postfix) with ESMTP id 5DC17156E42D for <9fans@9fans.net>; Mon, 16 Dec 2019 18:53:45 -0800 (PST) To: 9fans <9fans@9fans.net> Subject: Re: [9fans] dc(1) exponent limits In-reply-to: Your message of "Mon, 16 Dec 2019 18:28:35 -0800." <20191217022843.1A4ED156E42D@mail.bitblocks.com> References: <20191217022843.1A4ED156E42D@mail.bitblocks.com> Comments: In-reply-to Bakul Shah message dated "Mon, 16 Dec 2019 18:28:35 -0800." From: Bakul Shah MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-ID: <51942.1576551225.1@bitblocks.com> Content-Transfer-Encoding: 8bit Date: Mon, 16 Dec 2019 18:53:45 -0800 Message-Id: <20191217025352.5DC17156E42D@mail.bitblocks.com> Topicbox-Policy-Reasoning: allow: sender is a member Topicbox-Message-UUID: 786b5c40-2078-11ea-92d4-abeca68f29ac On Mon, 16 Dec 2019 18:28:35 -0800 Bakul Shah wrote: > 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. Forgot to add that dc's "bignum" representation is base 100 (each 0..99 "digit" can be stored in a byte). Go's math/big seems to use a number base that is machine word size (2^32 or 2^64). This means dc has a bigger constant multiplier (the big O notation hides this).