Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ConvertStringToDouble slightly wrong #2

Open
benibela opened this issue Jun 1, 2021 · 15 comments
Open

ConvertStringToDouble slightly wrong #2

benibela opened this issue Jun 1, 2021 · 15 comments

Comments

@benibela
Copy link

benibela commented Jun 1, 2021

I have run it with the test cases of https://github.com/nigeltao/parse-number-fxx-test-data and it finds many slightly broken numbers

For example:

parsing failed: 8.589934335999999523162841796875e+09 ( 8.5899343360000000E+009) got  8.5899343359999990E+009
parsing failed: 9008309105029287 ( 9.0083091050292880E+015) got  9.0083091050292860E+015
parsing failed: 9009640786128499 ( 9.0096407861285000E+015) got  9.0096407861284980E+015
parsing failed: 9009650242502435 ( 9.0096502425024360E+015) got  9.0096502425024340E+015
parsing failed: 9009859112919659 ( 9.0098591129196600E+015) got  9.0098591129196580E+015
parsing failed: 9010553528704491 ( 9.0105535287044920E+015) got  9.0105535287044900E+015
parsing failed: 9010674631189967 ( 9.0106746311899680E+015) got  9.0106746311899660E+015
parsing failed: 9011342073688603 ( 9.0113420736886040E+015) got  9.0113420736886020E+015
parsing failed: 9011683300034947 ( 9.0116833000349480E+015) got  9.0116833000349460E+015
parsing failed: 9013156506727407 ( 9.0131565067274080E+015) got  9.0131565067274060E+015

... parsingfail.txt

program Project1;

{$mode objfpc}{$H+}

uses sysutils, PasDblStrUtils;

var s, expected: string;
  t: TStringArray;
  d: double;
  code: integer;
  expectedU64: QWord;
  expectedD: double absolute expectedU64;
begin
  while not eof do begin
    try
      readln(s);
      t := s.split(' ');
      //val(t[3], d, code);
      //if code <> 0 then writeln(s);
      d := ConvertStringToDouble(t[3]);
      expected := '$'+t[2];
      val(expected, expectedU64, code);
      if code <> 0 then writeln('true failed: ',s);
      if expectedD <> d then
        writeln('parsing failed: ', t[3], ' (', expectedD, ') got ',d);
    except
      writeln('exception: ', s);
    end;
  end;
end.
@benibela
Copy link
Author

benibela commented Jun 1, 2021

After removing lines where the reference number and your number have the same absolute difference to the input number, three bad cases remain:



parsing failed: 2.22507385850720113605740979670913197593481954635164565e-308 (0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002225073858507201383090232717332404064219215980462331830553327416887204434813918195854283159012511020564067339731035811005152434161553460108856012385377718821130777993532002330479610147442583636071921565046942503734208375250806650616658158948720491179968591639648500635908770118304874799780887753749949451580451605050915399856582470818645113537935804992115981085766051992433352114352390148795699609591288891602992641511063466313393663477586513029371762047325631781485664350872122828637642044846811407613911477062801689853244110024161447421618567166150540154285084716752901903161322778896729707373123334086988983175067838846926092773977972858659654941091369095406136467568702398678315290680984617210924625396728515625 +2.47032822920623272088284396434110686180553327416887204434813918195854283159012511020564067339731035811005152434161553460108856012385377718821130777993532002330479610147442583636071921565046942503734208375250806650616658158948720491179968591639648500635908770118304874799780887753749949451580451605050915399856582470818645113537935804992115981085766051992433352114352390148795699609591288891602992641511063466313393663477586513029371762047325631781485664350872122828637642044846811407613911477062801689853244110024161447421618567166150540154285084716752901903161322778896729707373123334086988983175067838846926092773977972858659654941091369095406136467568702398678315290680984617210924625396728515625E-324) 
got 0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000022250738585072008890245868760858598876504231122409594654935248025624400092282356951787758888037591552642309780950434312085877387158357291821993020294379224223559819827501242041788969571311791082261043971979604000454897391938079198936081525613113376149842043271751033627391549782731594143828136275113838604094249464942286316695429105080201815926642134996606517803095075913058719846423906068637102005108723282784678843631944515866135041223479014792369585208321597621066375401613736583044193603714778355306682834535634005074073040135602968046375918583163124224521599262546494300836851861719422417646455137135420132217031370496583210154654068035397417906022589503023501937519773030945763173210852507299305089761582519159720757232455434770912461317493580281734466552734375 +-2.470328229206232720882843964341106861845064751974375599907717643048212241111962408447357690219049565687914122612841642708178006979705620775776440180172498757958211030428688208917738956028020395999545102608061920801063918474386886623850157956728248966372608450217268405856171863724886161395905750535057713683304570894919798184073357865003393482196904924086941280153576093931362897994891276717215321156368055484133864958776520985207630414791678402378933624598386263416955806396285221644693317165464365994925926959864397031953624081416836875775478400737453505699163148138280577582353544862864579867782968629503416789845345931964602582093977410496976498062480226969054236826789147492700694910238417480840279242767544565229087538682506419718265533447265625E-324

parsing failed: 0.999999999999999944488848768742172978818416595458984376 (1 +5.5511151231257827021181583404541015624E-17) 
got 0.99999999999999988897769753748434595763683319091796875 +-5.5511151231257827021181583404541015626E-17

parsing failed: 1.00000000000000011102230246251565404236316680908203126 (1.0000000000000002220446049250313080847263336181640625 +1.1102230246251565404236316680908203124E-16) 
got 1 +-1.1102230246251565404236316680908203126E-16

And a few overflows cases:

parsing failed: 8e938662882 (                    +Inf) got  0.0000000000000000E+000
parsing failed: 8e938662882 (                    +Inf) got  0.0000000000000000E+000
parsing failed: 1.00000000001e-2147483638 ( 0.0000000000000000E+000) got                     +Inf
parsing failed: 1e-00011111111111 ( 0.0000000000000000E+000) got                     +Inf
exception: 0000 00000000 0000000000000000 1e-21474836311
parsing failed: 1e-2147483648 ( 0.0000000000000000E+000) got                     +Inf
parsing failed: 1e+9223372036854775807 (                    +Inf) got  1.0000000000000001E-001

@BeRo1985
Copy link
Owner

BeRo1985 commented Jun 2, 2021

Please recheck with the lastest version, where I've added Ryu-style algorithm variants.

@benibela
Copy link
Author

benibela commented Jun 3, 2021

Now it is better, but still three clearly wrong cases:

parsing failed: 2.22507385850720113605740979670913197593481954635164565e-308 (0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002225073858507201383090232717332404064219215980462331830553327416887204434813918195854283159012511020564067339731035811005152434161553460108856012385377718821130777993532002330479610147442583636071921565046942503734208375250806650616658158948720491179968591639648500635908770118304874799780887753749949451580451605050915399856582470818645113537935804992115981085766051992433352114352390148795699609591288891602992641511063466313393663477586513029371762047325631781485664350872122828637642044846811407613911477062801689853244110024161447421618567166150540154285084716752901903161322778896729707373123334086988983175067838846926092773977972858659654941091369095406136467568702398678315290680984617210924625396728515625 
+ 2.47032822920623272088284396434110686180553327416887204434813918195854283159012511020564067339731035811005152434161553460108856012385377718821130777993532002330479610147442583636071921565046942503734208375250806650616658158948720491179968591639648500635908770118304874799780887753749949451580451605050915399856582470818645113537935804992115981085766051992433352114352390148795699609591288891602992641511063466313393663477586513029371762047325631781485664350872122828637642044846811407613911477062801689853244110024161447421618567166150540154285084716752901903161322778896729707373123334086988983175067838846926092773977972858659654941091369095406136467568702398678315290680984617210924625396728515625E-324) 
got 0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000022250738585072008890245868760858598876504231122409594654935248025624400092282356951787758888037591552642309780950434312085877387158357291821993020294379224223559819827501242041788969571311791082261043971979604000454897391938079198936081525613113376149842043271751033627391549782731594143828136275113838604094249464942286316695429105080201815926642134996606517803095075913058719846423906068637102005108723282784678843631944515866135041223479014792369585208321597621066375401613736583044193603714778355306682834535634005074073040135602968046375918583163124224521599262546494300836851861719422417646455137135420132217031370496583210154654068035397417906022589503023501937519773030945763173210852507299305089761582519159720757232455434770912461317493580281734466552734375 
+-2.470328229206232720882843964341106861845064751974375599907717643048212241111962408447357690219049565687914122612841642708178006979705620775776440180172498757958211030428688208917738956028020395999545102608061920801063918474386886623850157956728248966372608450217268405856171863724886161395905750535057713683304570894919798184073357865003393482196904924086941280153576093931362897994891276717215321156368055484133864958776520985207630414791678402378933624598386263416955806396285221644693317165464365994925926959864397031953624081416836875775478400737453505699163148138280577582353544862864579867782968629503416789845345931964602582093977410496976498062480226969054236826789147492700694910238417480840279242767544565229087538682506419718265533447265625E-324

parsing failed: 0.999999999999999944488848768742172978818416595458984376 
(1 +5.5511151231257827021181583404541015624E-17) 
got 0.99999999999999988897769753748434595763683319091796875 
+-5.5511151231257827021181583404541015626E-17


parsing failed: 1.00000000000000011102230246251565404236316680908203126 
(1.0000000000000002220446049250313080847263336181640625 
+1.1102230246251565404236316680908203124E-16) 
got 1 +-1.1102230246251565404236316680908203126E-16

And more including equidistance ones:

parsing failed: 8.589934335999999523162841796875e+09 (8589934336 +4.76837158203125E-7) got 8589934335.99999904632568359375 +-4.76837158203125E-7
parsing failed: 111111110000000000000 (111111110000000008192 +8.192E3) got 111111109999999991808 +-8.192E3
parsing failed: 10141204801825834649023672221696 (10141204801825835211973625643008 +5.62949953421312E14) got 10141204801825834086073718800384 +-5.62949953421312E14
parsing failed: 5708990770823839207320493820740630171355185152 (5708990770823839524233143877797980545530986496 +3.16912650057057350374175801344E29) got 5708990770823838890407843763683279797179383808 +-3.16912650057057350374175801344E29
parsing failed: 6250000000000000000000000000000000e-12 (6249999999999999475712 +-5.24288E5) got 6250000000000000524288 +5.24288E5
parsing failed: 280000000000000000000000 (280000000000000016777216 +1.6777216E7) got 279999999999999983222784 +-1.6777216E7
parsing failed: 2.22507385850720113605740979670913197593481954635164565e-308 (0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002225073858507201383090232717332404064219215980462331830553327416887204434813918195854283159012511020564067339731035811005152434161553460108856012385377718821130777993532002330479610147442583636071921565046942503734208375250806650616658158948720491179968591639648500635908770118304874799780887753749949451580451605050915399856582470818645113537935804992115981085766051992433352114352390148795699609591288891602992641511063466313393663477586513029371762047325631781485664350872122828637642044846811407613911477062801689853244110024161447421618567166150540154285084716752901903161322778896729707373123334086988983175067838846926092773977972858659654941091369095406136467568702398678315290680984617210924625396728515625 +2.47032822920623272088284396434110686180553327416887204434813918195854283159012511020564067339731035811005152434161553460108856012385377718821130777993532002330479610147442583636071921565046942503734208375250806650616658158948720491179968591639648500635908770118304874799780887753749949451580451605050915399856582470818645113537935804992115981085766051992433352114352390148795699609591288891602992641511063466313393663477586513029371762047325631781485664350872122828637642044846811407613911477062801689853244110024161447421618567166150540154285084716752901903161322778896729707373123334086988983175067838846926092773977972858659654941091369095406136467568702398678315290680984617210924625396728515625E-324) got 0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000022250738585072008890245868760858598876504231122409594654935248025624400092282356951787758888037591552642309780950434312085877387158357291821993020294379224223559819827501242041788969571311791082261043971979604000454897391938079198936081525613113376149842043271751033627391549782731594143828136275113838604094249464942286316695429105080201815926642134996606517803095075913058719846423906068637102005108723282784678843631944515866135041223479014792369585208321597621066375401613736583044193603714778355306682834535634005074073040135602968046375918583163124224521599262546494300836851861719422417646455137135420132217031370496583210154654068035397417906022589503023501937519773030945763173210852507299305089761582519159720757232455434770912461317493580281734466552734375 +-2.470328229206232720882843964341106861845064751974375599907717643048212241111962408447357690219049565687914122612841642708178006979705620775776440180172498757958211030428688208917738956028020395999545102608061920801063918474386886623850157956728248966372608450217268405856171863724886161395905750535057713683304570894919798184073357865003393482196904924086941280153576093931362897994891276717215321156368055484133864958776520985207630414791678402378933624598386263416955806396285221644693317165464365994925926959864397031953624081416836875775478400737453505699163148138280577582353544862864579867782968629503416789845345931964602582093977410496976498062480226969054236826789147492700694910238417480840279242767544565229087538682506419718265533447265625E-324
parsing failed: 0.999999999999999944488848768742172978818416595458984375 (1 +5.5511151231257827021181583404541015625E-17) got 0.99999999999999988897769753748434595763683319091796875 +-5.5511151231257827021181583404541015625E-17
parsing failed: 0.999999999999999944488848768742172978818416595458984376 (1 +5.5511151231257827021181583404541015624E-17) got 0.99999999999999988897769753748434595763683319091796875 +-5.5511151231257827021181583404541015626E-17
parsing failed: 1.00000000000000011102230246251565404236316680908203126 (1.0000000000000002220446049250313080847263336181640625 +1.1102230246251565404236316680908203124E-16) got 1 +-1.1102230246251565404236316680908203126E-16
parsing failed: 9223372036854775296.0 (9223372036854775808 +5.12E2) got 9223372036854774784 +-5.12E2
parsing failed: 10141204801825834649023672221696 (10141204801825835211973625643008 +5.62949953421312E14) got 10141204801825834086073718800384 +-5.62949953421312E14
parsing failed: 5708990770823839207320493820740630171355185152 (5708990770823839524233143877797980545530986496 +3.16912650057057350374175801344E29) got 5708990770823838890407843763683279797179383808 +-3.16912650057057350374175801344E29
parsing failed: 8.589934335999999523162841796875e+09 (8589934336 +4.76837158203125E-7) got 8589934335.99999904632568359375 +-4.76837158203125E-7
parsing failed: 13742728082020150272 (13742728082020151296 +1.024E3) got 13742728082020149248 +-1.024E3
parsing failed: 111111110000000000000 (111111110000000008192 +8.192E3) got 111111109999999991808 +-8.192E3
parsing failed: 95950276620332646268928 (95950276620332654657536 +8.388608E6) got 95950276620332637880320 +-8.388608E6
parsing failed: 228932440487179403132928 (228932440487179419910144 +1.6777216E7) got 228932440487179386355712 +-1.6777216E7
parsing failed: 510530141380583845003264 (510530141380583878557696 +3.3554432E7) got 510530141380583811448832 +-3.3554432E7
parsing failed: 584381888822081044348928 (584381888822081077903360 +3.3554432E7) got 584381888822081010794496 +-3.3554432E7
parsing failed: 625689337211426911027200 (625689337211426978136064 +6.7108864E7) got 625689337211426843918336 +-6.7108864E7
parsing failed: 832385771129895460536320 (832385771129895527645184 +6.7108864E7) got 832385771129895393427456 +-6.7108864E7
parsing failed: 908627438519900539191296 (908627438519900606300160 +6.7108864E7) got 908627438519900472082432 +-6.7108864E7
parsing failed: 10141204801825834649023672221696 (10141204801825835211973625643008 +5.62949953421312E14) got 10141204801825834086073718800384 +-5.62949953421312E14
parsing failed: 5708990770823839207320493820740630171355185152 (5708990770823839524233143877797980545530986496 +3.16912650057057350374175801344E29) got 5708990770823838890407843763683279797179383808 +-3.16912650057057350374175801344E29

@benibela
Copy link
Author

benibela commented Jun 3, 2021

That was for calling ConvertStringToDouble. Calling RyuStringToDouble directly is worse:

parsing failed: 2.16656806400000023841857910156251e9 (2166568064.000000476837158203125 +2.3841857910156249E-7) got 2166568064 +-2.3841857910156251E-7
parsing failed: 8.589934335999999523162841796875e+09 (8589934336 +4.76837158203125E-7) got 8589934335.99999904632568359375 +-4.76837158203125E-7
parsing failed: 14078544813052222467 (14078544813052223488 +1.021E3) got 14078544813052221440 +-1.027E3
parsing failed: 14237385024730686469 (14237385024730687488 +1.019E3) got 14237385024730685440 +-1.029E3
parsing failed: 27949676547093071875 (27949676547093073920 +2.045E3) got 27949676547093069824 +-2.051E3
parsing failed: 29786403316803561476 (29786403316803563520 +2.044E3) got 29786403316803559424 +-2.052E3
parsing failed: 34749545309385152514 (34749545309385154560 +2.046E3) got 34749545309385150464 +-2.05E3
parsing failed: 76411734731577139202 (76411734731577147392 +8.19E3) got 76411734731577131008 +-8.194E3
parsing failed: 111012772567089864771 (111012772567089872896 +8.125E3) got 111012772567089856512 +-8.259E3
parsing failed: 134640979294615609375 (134640979294615617536 +8.161E3) got 134640979294615601152 +-8.223E3
parsing failed: 186374920284604481572 (186374920284604497920 +1.6348E4) got 186374920284604465152 +-1.642E4
parsing failed: 270197914991684796438 (270197914991684812800 +1.6362E4) got 270197914991684780032 +-1.6406E4
parsing failed: 277591217732240982056 (277591217732240998400 +1.6344E4) got 277591217732240965632 +-1.6424E4
parsing failed: 297413421753270042664 (297413421753270075392 +3.2728E4) got 297413421753270009856 +-3.2808E4
parsing failed: 321381981418280026116 (321381981418280058880 +3.2764E4) got 321381981418279993344 +-3.2772E4
parsing failed: 1126305374559809765625 (1126305374559809830912 +6.5287E4) got 1126305374559809699840 +-6.5785E4
parsing failed: 1547992468664497602731 (1547992468664497733632 +1.30901E5) got 1547992468664497471488 +-1.31243E5
parsing failed: 5870271506626281734498 (5870271506626282258432 +5.23934E5) got 5870271506626281209856 +-5.24642E5
parsing failed: 8274577754023106445313 (8274577754023106969600 +5.24287E5) got 8274577754023105921024 +-5.24289E5
parsing failed: 11545416679747224609375 (11545416679747225649152 +1.039777E6) got 11545416679747223552000 +-1.057375E6
parsing failed: 13227067767527654296875 (13227067767527655342080 +1.045205E6) got 13227067767527653244928 +-1.051947E6
parsing failed: 17403220598228945732117 (17403220598228946780160 +1.048043E6) got 17403220598228944683008 +-1.049109E6
parsing failed: 80803951093300856882706 (80803951093300865269760 +8.387054E6) got 80803951093300848492544 +-8.390162E6
parsing failed: 121622650418780700683594 (121622650418780709060608 +8.377014E6) got 121622650418780692283392 +-8.400202E6
parsing failed: 251600155466914208984375 (251600155466914225717248 +1.6732873E7) got 251600155466914192162816 +-1.6821559E7
parsing failed: 1053683582720806121826172 (1053683582720806188220416 +6.6394244E7) got 1053683582720806054002688 +-6.7823484E7
parsing failed: 2038277782155894775390625 (2038277782155894909304832 +1.33914207E8) got 2038277782155894640869376 +-1.34521249E8
parsing failed: 12802872898842514038085938 (12802872898842515109576704 +1.071490766E9) got 12802872898842512962093056 +-1.075992882E9
parsing failed: 26566581654020684957504272 (26566581654020687099068416 +2.141564144E9) got 26566581654020682804101120 +-2.153403152E9
parsing failed: 389685336901682281494140625 (389685336901682315801919488 +3.4307778863E10) got 389685336901682247082442752 +-3.4411697873E10
parsing failed: 10141204801825834649023672221696 (10141204801825835211973625643008 +5.62949953421312E14) got 10141204801825834086073718800384 +-5.62949953421312E14
parsing failed: 5708990770823839207320493820740630171355185152 (5708990770823839524233143877797980545530986496 +3.16912650057057350374175801344E29) got 5708990770823838890407843763683279797179383808 +-3.16912650057057350374175801344E29
parsing failed: 1090544144181609348835077142190 (1090544144181609419040633126912 +7.0205555984722E13) got 1090544144181609278303144771584 +-7.0531932370606E13
parsing failed: 1090544144181609348835077142190 (1090544144181609419040633126912 +7.0205555984722E13) got 1090544144181609278303144771584 +-7.0531932370606E13
parsing failed: 2.22507385850720113605740979670913197593481954635164565e-308 (0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002225073858507201383090232717332404064219215980462331830553327416887204434813918195854283159012511020564067339731035811005152434161553460108856012385377718821130777993532002330479610147442583636071921565046942503734208375250806650616658158948720491179968591639648500635908770118304874799780887753749949451580451605050915399856582470818645113537935804992115981085766051992433352114352390148795699609591288891602992641511063466313393663477586513029371762047325631781485664350872122828637642044846811407613911477062801689853244110024161447421618567166150540154285084716752901903161322778896729707373123334086988983175067838846926092773977972858659654941091369095406136467568702398678315290680984617210924625396728515625 +2.47032822920623272088284396434110686180553327416887204434813918195854283159012511020564067339731035811005152434161553460108856012385377718821130777993532002330479610147442583636071921565046942503734208375250806650616658158948720491179968591639648500635908770118304874799780887753749949451580451605050915399856582470818645113537935804992115981085766051992433352114352390148795699609591288891602992641511063466313393663477586513029371762047325631781485664350872122828637642044846811407613911477062801689853244110024161447421618567166150540154285084716752901903161322778896729707373123334086988983175067838846926092773977972858659654941091369095406136467568702398678315290680984617210924625396728515625E-324) got 0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000022250738585072008890245868760858598876504231122409594654935248025624400092282356951787758888037591552642309780950434312085877387158357291821993020294379224223559819827501242041788969571311791082261043971979604000454897391938079198936081525613113376149842043271751033627391549782731594143828136275113838604094249464942286316695429105080201815926642134996606517803095075913058719846423906068637102005108723282784678843631944515866135041223479014792369585208321597621066375401613736583044193603714778355306682834535634005074073040135602968046375918583163124224521599262546494300836851861719422417646455137135420132217031370496583210154654068035397417906022589503023501937519773030945763173210852507299305089761582519159720757232455434770912461317493580281734466552734375 +-2.470328229206232720882843964341106861845064751974375599907717643048212241111962408447357690219049565687914122612841642708178006979705620775776440180172498757958211030428688208917738956028020395999545102608061920801063918474386886623850157956728248966372608450217268405856171863724886161395905750535057713683304570894919798184073357865003393482196904924086941280153576093931362897994891276717215321156368055484133864958776520985207630414791678402378933624598386263416955806396285221644693317165464365994925926959864397031953624081416836875775478400737453505699163148138280577582353544862864579867782968629503416789845345931964602582093977410496976498062480226969054236826789147492700694910238417480840279242767544565229087538682506419718265533447265625E-324
parsing failed: 0.999999999999999944488848768742172978818416595458984375 (1 +5.5511151231257827021181583404541015625E-17) got 0.99999999999999988897769753748434595763683319091796875 +-5.5511151231257827021181583404541015625E-17
parsing failed: 0.999999999999999944488848768742172978818416595458984376 (1 +5.5511151231257827021181583404541015624E-17) got 0.99999999999999988897769753748434595763683319091796875 +-5.5511151231257827021181583404541015626E-17
parsing failed: 1.00000000000000011102230246251565404236316680908203126 (1.0000000000000002220446049250313080847263336181640625 +1.1102230246251565404236316680908203124E-16) got 1 +-1.1102230246251565404236316680908203126E-16
parsing failed: 10141204801825834649023672221696 (10141204801825835211973625643008 +5.62949953421312E14) got 10141204801825834086073718800384 +-5.62949953421312E14
parsing failed: 1014120480182583464902367222169600001e-5 (10141204801825835211973625643008 +5.6294995342131199999E14) got 10141204801825834086073718800384 +-5.6294995342131200001E14
parsing failed: 5708990770823839207320493820740630171355185152 (5708990770823839524233143877797980545530986496 +3.16912650057057350374175801344E29) got 5708990770823838890407843763683279797179383808 +-3.16912650057057350374175801344E29
parsing failed: 5708990770823839207320493820740630171355185152001e-3 (5708990770823839524233143877797980545530986496 +3.16912650057057350374175801343999E29) got 5708990770823838890407843763683279797179383808 +-3.16912650057057350374175801344001E29
parsing failed: 2.16656806400000023841857910156251e9 (2166568064.000000476837158203125 +2.3841857910156249E-7) got 2166568064 +-2.3841857910156251E-7
parsing failed: 8.589934335999999523162841796875e+09 (8589934336 +4.76837158203125E-7) got 8589934335.99999904632568359375 +-4.76837158203125E-7
parsing failed: 10052108125844341766 (10052108125844342784 +1.018E3) got 10052108125844340736 +-1.03E3
parsing failed: 13742728082020150272 (13742728082020151296 +1.024E3) got 13742728082020149248 +-1.024E3
parsing failed: 14078544813052222467 (14078544813052223488 +1.021E3) got 14078544813052221440 +-1.027E3
parsing failed: 14151565162110759939 (14151565162110760960 +1.021E3) got 14151565162110758912 +-1.027E3
parsing failed: 14237385024730686469 (14237385024730687488 +1.019E3) got 14237385024730685440 +-1.029E3
parsing failed: 18379969808252713988 (18379969808252715008 +1.02E3) got 18379969808252712960 +-1.028E3
parsing failed: 27949676547093071875 (27949676547093073920 +2.045E3) got 27949676547093069824 +-2.051E3
parsing failed: 29786403316803561476 (29786403316803563520 +2.044E3) got 29786403316803559424 +-2.052E3
parsing failed: 34749545309385152514 (34749545309385154560 +2.046E3) got 34749545309385150464 +-2.05E3
parsing failed: 76411734731577139202 (76411734731577147392 +8.19E3) got 76411734731577131008 +-8.194E3
parsing failed: 111012772567089864771 (111012772567089872896 +8.125E3) got 111012772567089856512 +-8.259E3
parsing failed: 134640979294615609375 (134640979294615617536 +8.161E3) got 134640979294615601152 +-8.223E3
parsing failed: 186374920284604481572 (186374920284604497920 +1.6348E4) got 186374920284604465152 +-1.642E4
parsing failed: 270197914991684796438 (270197914991684812800 +1.6362E4) got 270197914991684780032 +-1.6406E4
parsing failed: 277591217732240982056 (277591217732240998400 +1.6344E4) got 277591217732240965632 +-1.6424E4
parsing failed: 297413421753270042664 (297413421753270075392 +3.2728E4) got 297413421753270009856 +-3.2808E4
parsing failed: 321381981418280026116 (321381981418280058880 +3.2764E4) got 321381981418279993344 +-3.2772E4
parsing failed: 1126305374559809765625 (1126305374559809830912 +6.5287E4) got 1126305374559809699840 +-6.5785E4
parsing failed: 1547992468664497602731 (1547992468664497733632 +1.30901E5) got 1547992468664497471488 +-1.31243E5
parsing failed: 5870271506626281734498 (5870271506626282258432 +5.23934E5) got 5870271506626281209856 +-5.24642E5
parsing failed: 8274577754023106445313 (8274577754023106969600 +5.24287E5) got 8274577754023105921024 +-5.24289E5
parsing failed: 11545416679747224609375 (11545416679747225649152 +1.039777E6) got 11545416679747223552000 +-1.057375E6
parsing failed: 13227067767527654296875 (13227067767527655342080 +1.045205E6) got 13227067767527653244928 +-1.051947E6
parsing failed: 17403220598228945732117 (17403220598228946780160 +1.048043E6) got 17403220598228944683008 +-1.049109E6
parsing failed: 80803951093300856882706 (80803951093300865269760 +8.387054E6) got 80803951093300848492544 +-8.390162E6
parsing failed: 95950276620332646268928 (95950276620332654657536 +8.388608E6) got 95950276620332637880320 +-8.388608E6
parsing failed: 121622650418780700683594 (121622650418780709060608 +8.377014E6) got 121622650418780692283392 +-8.400202E6
parsing failed: 228932440487179403132928 (228932440487179419910144 +1.6777216E7) got 228932440487179386355712 +-1.6777216E7
parsing failed: 251600155466914208984375 (251600155466914225717248 +1.6732873E7) got 251600155466914192162816 +-1.6821559E7
parsing failed: 510530141380583845003264 (510530141380583878557696 +3.3554432E7) got 510530141380583811448832 +-3.3554432E7
parsing failed: 584381888822081044348928 (584381888822081077903360 +3.3554432E7) got 584381888822081010794496 +-3.3554432E7
parsing failed: 625689337211426911027200 (625689337211426978136064 +6.7108864E7) got 625689337211426843918336 +-6.7108864E7
parsing failed: 832385771129895460536320 (832385771129895527645184 +6.7108864E7) got 832385771129895393427456 +-6.7108864E7
parsing failed: 908627438519900539191296 (908627438519900606300160 +6.7108864E7) got 908627438519900472082432 +-6.7108864E7
parsing failed: 1053683582720806121826172 (1053683582720806188220416 +6.6394244E7) got 1053683582720806054002688 +-6.7823484E7
parsing failed: 2038277782155894775390625 (2038277782155894909304832 +1.33914207E8) got 2038277782155894640869376 +-1.34521249E8
parsing failed: 8128080666065216064453125 (8128080666065216601063424 +5.36610299E8) got 8128080666065215527321600 +-5.37131525E8
parsing failed: 12802872898842514038085938 (12802872898842515109576704 +1.071490766E9) got 12802872898842512962093056 +-1.075992882E9
parsing failed: 26566581654020684957504272 (26566581654020687099068416 +2.141564144E9) got 26566581654020682804101120 +-2.153403152E9
parsing failed: 389685336901682281494140625 (389685336901682315801919488 +3.4307778863E10) got 389685336901682247082442752 +-3.4411697873E10
parsing failed: 26350434346072337605128617984 (26350434346072339802004389888 +2.196875771904E12) got 26350434346072335403957878784 +-2.2011707392E12
parsing failed: 10141204801825834649023672221696 (10141204801825835211973625643008 +5.62949953421312E14) got 10141204801825834086073718800384 +-5.62949953421312E14
parsing failed: 63429291159263812005519866943359375 (63429291159263816616139089399250944 +4.610619222455891569E18) got 63429291159263807392767052544475136 +-4.612752814398884239E18
parsing failed: 5708990770823839207320493820740630171355185152 (5708990770823839524233143877797980545530986496 +3.16912650057057350374175801344E29) got 5708990770823838890407843763683279797179383808 +-3.16912650057057350374175801344E29
parsing failed: 100000000000000006552261095746787856411749967010355244012076385661777528108930437151694716 (100000000000000013610143093418879568982174616394030302241812869736859973511157455477800960 +7.057881997672091712570424649383675058229736484075082445402227018326106244E72) got 99999999999999999475366575191804932315794610450682175621941694731908308538307845136842752 +-7.076894520554982924095955356559673068390134690929869219570622592014851964E72
parsing failed: 100519131923249665159539189045738250625445899193224853577560494867813212309547435281219657 (100519131923249672217212462924242430833549440629923749246629767339345635062920739289038848 +7.057673273878504180208103541436698895669069272471532422753373304007819191E72) got 100519131923249658082435944697167794167169434686575622626758592334393970090071128948080640 +-7.077103244348570456458276464506649230950801902533419242219476306333139017E72
parsing failed: 111564952075406614182531648091854721622728917132349914943806626132966165315408652445964842 (111564952075406621243639787074136923715630479522827601044420118479456277204100535900176384 +7.061108138982282202092901562390477686100613492346490111888691883454211542E72) got 111564952075406607108863268847062287049250473579479474424548943474504612231250925559218176 +-7.073668379244792434573478443552870440519257682658461553084157726886746666E72
parsing failed: 119038536450898425044770684828672070243333428291577919705134892889011156980930242366813130 (119038536450898432081766531288609352100081840765287723490601172219147626575801152643792896 +7.036995846459937281856748412473709803785466279330136469594870910276979766E72) got 119038536450898417946990013061534715433701834821939596870729997214195961602951542302834688 +-7.097780671767137354809631593469638322834404895674815195377978700063978442E72
parsing failed: 120732258617281579976366131392745072658904926119270002620328679520460157302155135408495181 (120732258617281587001462848240964610528375890199107665209714073857173548085613780436779008 +7.025096716848219537869470964079837662589385394336713390783458645028283827E72) got 120732258617281572866686330013889973861995884255759538589842898852221883112764170095820800 +-7.109679801378855098796909041863510464030485780668238274189390965312674381E72
parsing failed: 155745657801592923772881793223280483883092323373037500307786125097119085019518098311626516 (155745657801592937866429542558394142637924836089289116972821509661488009079393387433426944 +1.4093547749335113658754832512716251616665035384564368924059875289121800428E73) got 155745657801592909596876506104244869305164824202592863733079159651584679133694166751510528 +-1.4176005287119035614577927499170444636574706965445534405885823931560115988E73
parsing failed: 226753480935212068872259503118509581066207485830029333326409179897675170932942171931932924 (226753480935212082935865372972199848095991859678428908276650924977229583582593649202954240 +1.4063605869853690267029784373848399574950241745079554412649651477271021316E73) got 226753480935212054666312336518050574763231847791732655036908574967326253636894428521037824 +-1.42059471666004590063029756380382966782895006049303489172960477434108951E73
parsing failed: 896685649750398556670281450079476171301511416012248448222007463781644071630086456019890128 (896685649750398613185416931484349669864081890896706265726549327660807344297720396759695360 +5.6515135481404873498562570474884457817504541863879163272667633940739805232E73) got 896685649750398500107204785667752576533041843349921252767579927621194024514923514032029696 +-5.6563076664411723594768469572662327195454427536160450047115162941987860432E73
parsing failed: 988535911477486186638825422692833263124125301283449371615913399670578555429637516523307869 (988535911477486243164177441761068400936763251695779703850162972143461678433503360575340544 +5.6525352019068235137812637950412330332234249572472883123003865844052032675E73) got 988535911477486130085965295944471307605723204148994690891193572103848358650706477847674880 +-5.6552860126748361955518402097134454680724719827566730196778931038675632989E73
parsing failed: 999926968179542852977888064283788338863669429270136082147712570640533209564082812219258592 (999926968179542909459989400406523223389962895280644467005486933910293971093265356374933504 +5.6482101336122734884526293466010508384857774363269760761529182544155674912E73) got 999926968179542796381777254589926130058922847733859454046517533870680651310468473647267840 +-5.6596110809693862208804746581536276628101195036769852558253614338571990752E73

@BeRo1985
Copy link
Owner

BeRo1985 commented Jun 3, 2021

Hm ok, then I will port the offical Ryu test cases to Pascal (from https://github.com/ulfjack/ryu/blob/master/ryu/tests/ ). for to see further.

@BeRo1985
Copy link
Owner

BeRo1985 commented Jun 3, 2021

So, I've ported the relevant parts of the offical Ryu test cases to Pascal, which passes also as whole without one error.

So what is left are probably then Ryu-Algorihm concept conditional differences to ensure e.g. roundtrips and other special characteristics. And since the Ryu paper ( https://dl.acm.org/citation.cfm?doid=3296979.3192369 ) has been peer reviewed several times, and since the one paper has also complete correctness proof of the algorithm, I would classify the Ryu algo as correct here. Even my reimplementation so far, since it passes also all offical Ryu testcase tests.

The only difference to the original C implementation of the Ryu algorithm so far is that my reimplementation has no limit to a maximum count of to parsing 17 digits by dynamically truncating and roundig all further digits when needed.

But please recheck it again anyway :-)

@nigeltao
Copy link

nigeltao commented Jun 4, 2021

See discussion at
nigeltao/parse-number-fxx-test-data#1

@benibela
Copy link
Author

benibela commented Jun 4, 2021 via email

@BeRo1985
Copy link
Owner

BeRo1985 commented Jun 4, 2021

So, after reading https://www.exploringbinary.com/decimal-to-floating-point-needs-arbitrary-precision/ i've reworked the slow path double parsing by parsing to a temporary 512-bit floaing point value, which breaking-tie-even-rounded down to a 64-bit floating point afterwards. But this new slow path is damn slow. So i'll implement more fine-tuned algo variants in between in the next days, from very fast (Eisel-Lemire), then fast (ryu) and then to damn slow (float512).

Anyway, please recheck it. :-)

@benibela
Copy link
Author

benibela commented Jun 5, 2021

So i'll implement more fine-tuned algo variants in between in the next days, from very fast (Eisel-Lemire), then fast (ryu) and then to damn slow (float512).

That would be perfect

Perhaps this is faster than damn slow: https://nigeltao.github.io/blog/2020/parse-number-f64-simple.html ?

@BeRo1985
Copy link
Owner

BeRo1985 commented Jun 6, 2021

I have now implemented an additional a bit faster but still slow big-integer-based "Algorithm M" fallback path, but it currently only works for base 10. For the other bases (2 binary, 4, 8 octal, 16 hex) I will extend the algorithm in the next days, and when I am done with it, I will remove the old float512 fallback path.

@benibela
Copy link
Author

benibela commented Jun 6, 2021

The 64-bit version passes all these tests

But with the 32-bit version there seems to be a problem in ComputeFloat64.

    ComputeFloat64( -22 , 3053, ...) = 3.0530000000000002E-019     //32-bit

    ComputeFloat64( -22 , 3053, ...) = 3.0529999999999998E-019     //64-bit 

@BeRo1985
Copy link
Owner

BeRo1985 commented Jun 6, 2021

Ok it seems, I've found out the issue. It is, or better, it was the FPU-using fast path of ComputeFloat64. Maybe I should IFdef'ing it out as whole, except for x86-64 and AArch64.

@benibela
Copy link
Author

benibela commented Jun 6, 2021

So 32-bit used FPU and 64-bit used SSE. Then the 32-bit fast path works after SetPrecisionMode(pmDouble);

@BeRo1985
Copy link
Owner

BeRo1985 commented Jun 6, 2021

The big-integer-based "Algorithm M" fallback path can also process base 2, base 4, base 8 and base 16 inputs.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants