www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 5568] New: A problem with BigInt modulus

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5568

           Summary: A problem with BigInt modulus
           Product: D
           Version: D2
          Platform: x86
        OS/Version: Windows
            Status: NEW
          Keywords: wrong-code
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc



A similar Python program prints 0 at the third line, as the result of the
modulus operation (dmd 2.051):


import std.bigint: BigInt;
import std.stdio: writeln;

void writelnBitInt(BigInt i) {
    const(char)[] result;
    i.toString((const(char)[] s){ result = s; }, "d");
    writeln(result);
}

void main() {
    BigInt mp = (BigInt(1) << 9689) - 1;
    writelnBitInt(mp);
BigInt s = BigInt(
 "228694635060773045437410210051261085807396799690694517906644987298166" ~
 "6992376432989534870397812823305068417419079356591122919780338071905473" ~
 "6400613582074661719715945714870016839817365841690554441784772068325928" ~
 "1452714193898635389597524975004044059328266941252110031211836779083115" ~
 "5347993848682537303207843841506309515106701156999493715609430963134691" ~
 "0288583059102921184541925069062812331241888881668993818367866958354112" ~
 "2687899799821597449900062249947751459645073117432856825525199955559385" ~
 "6330192236992736233031227006143226657271647358180858961017199307890088" ~
 "0794518643558734808874648194818947655526101325976868950862878975787562" ~
 "9284644133732867955797990134605432410108894433615174259901027320032197" ~
 "5697280351285524440612303107202607725622786657027558936331392983520879" ~
 "7067641410148883128565223591044537124373409407332900053178040042176236" ~
 "4177129912598366398346464930052925571793421936988503434899568253732348" ~
 "4540414463660775213506424110461417372280832724154665963507743687792018" ~
 "9249382763503433649511016461187322182285166044920140977305517741499787" ~
 "1241348333333662694218751245117778785677048996977661678988533708334951" ~
 "2323147374214064479535510964833739624483177524808898216304740432637242" ~
 "9721341927949686869980301160672122722256892635895672790005624778454517" ~
 "0719591782333659881915816376802827842000042429694925267965965380231372" ~
 "9569983865026035991552816548562417341487057977773599309236599266861821" ~
 "3106482525405901731751780517652693159404762763065109918381814285922963" ~
 "9842278531563218633288069065779065422909715691584321509341252646462986" ~
 "5214470913899741432445075822986111755564956813425093522336077733332095" ~
 "2408266165899917224881330715498628835983225378111892227779176768886990" ~
 "0063234426095914014559294783758352123858802397025248243300921207625282" ~
 "8256509857201734944193746828286232783113117540610464994631613059515043" ~
 "9895213963149102291877334817845526772485964705929624726095661895705532" ~
 "0670116428419073656583224624200075674244735890411297092669501057348387" ~
 "6536184762181782535264056235428672657983077717129836038654792507550751" ~
 "7178188457680811826802345678700212792130270091239910158826411156667562" ~
 "5636433195421695229237467508589285573790750044911014469934531460477522" ~
 "6692974239406902790485934606008476276508073663538037473020669835418732" ~
 "1704353088397590646419947534811676969341485990918901498311415724280980" ~
 "2566250057369336775674814393849002260153352912826931350065982550258525" ~
 "1949313368235240589683777921538437364829276305928002877462588683281392" ~
 "9672391327894462383864968226524379036603628947143733413759126532446286" ~
 "7072422424648527542180323321702230700475454407339035925627012757950044" ~
 "2054385323474630350247715932648726599578733029166471894337517817623974" ~
 "1993136975881781023341491311916236320371052591744799881970257922104227" ~
 "9740043550348065022539561586651001862003909041303453684222916572891448" ~
 "6734567813695439769062200724540051206685532151502787818619266752574585" ~
 "2641245187934865321750810067063135065185163596122535345068195106275310" ~
 "8316522368466066970428516728039159568794560794801413454334401557045089" ~
 "2237644858070297385167863321233654953564890465310973192610950234355189" ~
 "9664256670878613603175976996179556114870938711373613431176934865473381" ~
 "2714717016047109324257021040793451604322252988549292112563395575046938" ~
 "0890527585965169451620767275447361506277660364205744260055342023628827" ~
 "8853555455082058531488488676046468095866950382861830389397841467185421" ~
 "7543432670174608279868912319424686445269307148735641336757006338190683" ~
 "2433475697359276112487070347034463001470300314459444518076918790629289" ~
 "4064843579526762699352468167960224244537725960480720411641493252938038" ~
 "4051638475283486383585795301912755669843341551181305902769891213568060" ~
 "5557529916970070239493701088405356378789904728175881597569574846704713" ~
 "5601645351220269526864564376372986389057176612464825177101057832702974" ~
 "3871869648194280474907626262429519225325387868941288256891343283127591" ~
 "8215437895587395209101054306738837656495538674684522946520377837726657" ~
 "6117402983329271683007478988619568285526330256399541183052393416379724" ~
 "5328712742277174346568820658350365460184855851563598729366735159501258" ~
 "8832675903129140587103905448260806602857156878550973318416515781410896" ~
 "3372168234053373973480257883363730328371932228628974198597665563730677" ~
 "2400610819948909173272266643411678434415191425373087470941851276692399" ~
 "7850992655275319858801646726201273665668446521227058948308288948553962" ~
 "7718789312050634948698177341245342102569626816228054039438004485068209" ~
 "6184225538648883417822729007797728899987511236787781584110579510647990" ~
 "9924399715141007817323815577771164193996330653884601434989159070496776" ~
 "4822343504652698950212077745252449805222196758591419978103356766693739" ~
 "0446825709042758146512320893656678419903588133453490274662807544187248" ~
 "5723787009800933924700614027702579550490148906791279060065411655285672" ~
 "8588807558555485608648887110555801620682364364209339668468592284062099" ~
 "8744699110536785335571609319429357055951869305283741704051736303649024" ~
 "4630309057467718496660602280293111196099819740368803898400415060653985" ~
 "5608793753688025280266257310999751574065150181446228157978600866430981" ~
 "2519107245785674533853195221612803968612813130525691685218494989634752" ~
 "9340694255948592554005046423106889679709276745766601105775808430730803" ~
 "1651218701169416077902225466538411427970046192995912609917499359548285" ~
 "8040137406773653943938953277783259382766679710557885475511160137694876" ~
 "9930860327605001466574189784953608703728992077974570317293138601093119" ~
 "8776494706890261887728393692303471620622488534241455024436527467372842" ~
 "3756254827535460236313789036316932901420366998614035756362211624747313" ~
 "3301860804833944192503612026491578205610972734595517402324169678519460" ~
 "4154405726182485114690238063403990282066496464825117530009064707504585" ~
 "8661908413027789189110810118006772679633531625325355059473520914072802" ~
 "2141053362268337433178693117844589416050690531695199298215498130606991" ~
 "2411544216041550606499839");
    writelnBitInt(s);
    s = s % mp;
    writelnBitInt(s);
}

-------------------------------

It comes from this D2 code:

import std.bigint: BigInt;
bool isMersennePrime(int p) {
    BigInt mp = (BigInt(1) << p) - 1;
    BigInt s  = BigInt(4);
    foreach (_; 3 .. p+1)
        s = (s * s - 2) % mp;
    return s == 0;
}
void main() {
    assert(isMersennePrime(9689));
}


And equivalent Python2 code:

def isMersennePrime(p):
    mp = (1 << p) - 1
    s  = 4
    for _ in xrange(3, p+1):
        s = (s * s - 2) % mp
    return s == 0
assert isMersennePrime(9689)

The assert in the Python code is satisfied because 9689 is a Mersenne prime.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 12 2011
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5568




Problem originally found by tsukikage.

A handy printing function for BigInts is really needed in Phobos.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 12 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5568


Don <clugdbug yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |clugdbug yahoo.com.au





 Problem originally found by tsukikage.
 
 A handy printing function for BigInts is really needed in Phobos.


Have you tried writefln?

import std.stdio;
import std.bigint;

void main()
{
    BigInt a = 7;
    a ^^=56;
    writefln("%x", a);
    writefln("%s", a);    
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 13 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5568







 Have you tried writefln?
 
 import std.stdio;
 import std.bigint;
 
 void main()
 {
     BigInt a = 7;
     a ^^=56;
     writefln("%x", a);
     writefln("%s", a);    
 }


I have never tried that. I suggest to add this example to docs of the
std.bigint module :-)

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 13 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5568







 

 Have you tried writefln?
 
 import std.stdio;
 import std.bigint;
 
 void main()
 {
     BigInt a = 7;
     a ^^=56;
     writefln("%x", a);
     writefln("%s", a);    
 }


 
 I have never tried that. I suggest to add this example to docs of the
 std.bigint module :-)


Yes, although I think it's pretty obvious. The non-obvious thing, is that if
you tried in on 2.050 or earlier, it didn't work... It does now.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 13 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5568




Reduced test case:

import std.bigint;
void main() {
    enum int Y = 2008;
    BigInt m = (BigInt(1) << (Y*1 + 1)) - 1;
    BigInt b = (BigInt(1) << (Y*2 + 1)) - 1;
    BigInt c = (BigInt(1) << (Y*3 + 1)) - 1;
    BigInt w =  c - b;
    w = w % m;
}

This trips an assert when Phobos is compiled in debug mode.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 19 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5568




And the original test case is:

import std.bigint;
void main() {
    BigInt m = (BigInt(1) << (4846+4843) ) - 1;
    BigInt a = (BigInt(1) << 4846 ) - 1;
    BigInt b = (BigInt(1) << (4846*2 + 4843)) - 1;
    BigInt c = (BigInt(1) << (4846*2 + 4843*2)) - 1;
    BigInt w =  c - b + a;
    assert(w % m == 0);
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 19 2011
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5568


Don <clugdbug yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED



Fixed:
https://github.com/D-Programming-Language/phobos/commit/9ecf947290f1149e1b062a75dafd30326697fe00

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 23 2011