Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder1.enfer-du-nord.net!feeder.news-service.com!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path: <ian.g.kelly@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.035
X-Spam-Evidence: '*H*': 0.93; '*S*': 0.00; 'used.': 0.07; 'am,': 0.13; 'wrote:': 0.15; 'eckhardt': 0.16; 'range.': 0.16; 'worse,': 0.16; 'header:In-Reply-To:1': 0.22; 'worst': 0.23; 'thu,': 0.28; 'message-id:@mail.gmail.com': 0.28; 'subject:number': 0.30; 'actually': 0.33; 'to:addr:python-list': 0.34; 'another': 0.38; 'received:google.com': 0.38; 'received:209.85.161': 0.38; 'received:209.85': 0.38; 'subject:: ': 0.38; 'two': 0.38; 'to:addr:python.org': 0.39; 'received:209': 0.40; 'below': 0.62
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type:content-transfer-encoding; bh=pHlaaJRByBoxn78IFxIIsGYyruv97lWGIp0A6jipMmg=; b=CYMHD9OV+HIN5F3GaRcjpNbneCZ0nJ7Y32vSePwHCJPd5cBNHwXtj3O9w1nw3EqeuV Da2Vv/09pvlvD9tXvzmHAOdc+PM27xLQKWyj2Gjp0KAiwPVZ8nl7rigR+Jj+uYdLRCav Y6yL/Wi+RohlVQ5CbY4OcBVJ+LsAEHZMG+lDM=
MIME-Version: 1.0
In-Reply-To: <m47ge8-j67.ln1@satorlaser.homedns.org>
References: <iv2d7n$ksv$1@speranza.aioe.org> <mailman.721.1309982555.1164.python-list@python.org> <iv2g6s$sl0$1@speranza.aioe.org> <m47ge8-j67.ln1@satorlaser.homedns.org>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Thu, 7 Jul 2011 09:49:10 -0600
Subject: Re: Large number multiplication
To: python-list@python.org
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.746.1310053781.1164.python-list@python.org>
Lines: 11
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1310053781 news.xs4all.nl 21863 [2001:888:2000:d::a6]:34185
X-Complaints-To: abuse@xs4all.nl
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:9034

On Thu, Jul 7, 2011 at 2:30 AM, Ulrich Eckhardt
<ulrich.eckhardt@dominolaser.com> wrote:
> Even worse, most people would actually pay for its use, because they don'=
t
> use numbers large enough to merit the Sch=F6nhage=96Strassen algorithm.

As it stands, Karatsuba is only used for numbers greater than a
specific threshold.  Adding Sch=F6nhage=96Strassen would just mean adding
another threshold, below which Karatsuba would still be used.  So at
worst it would just add another comparison or two for numbers within
the Karatsuba range.