{"header":{"message":"Change Nimber to FiniteNimber","description":null,"timestamp":"2024-05-09T23:57:10.406345521Z","authors":[{}]},"hash":"F2J33IDG7QQEVMUX7EEIWSV43BMGWET3EPTR4CUAZ5PZ7SFXIXFQC","authors":[{"key":"rodYtiEfBkWwnTMxdJCjgZfGA58pw5EzYYLWDptiSh1"}],"deps":{"hashes":[["F2J33IDG7QQEVMUX7EEIWSV43BMGWET3EPTR4CUAZ5PZ7SFXIXFQC","Change Nimber to FiniteNimber"],["AA",null],["ADE3QH6CJXDMZNXCPR7YTFLUHUV6TFP7Z3V7SMKUELP3JVGCACXQC","Add definition of mex operator"],["73K2ULQWAV2A2MICO4YYOVKX55WJYYHBBQSALBZQBKQJLYIDDPGQC","Use Numeric.Natural"],["VZUEVF2UF4O2S3SFZKSV45QBUMQQ5GVNQMYYFU5PXPFX344P7W3QC","Use fewer additions in recip"],["CEQIUHRVILZ2JCYTQPEK4LTHSKEZMMS3YXTE3L3ELGMW2RNOH7YQC","solveQuadratic returns solutions in order"],["3BR6NSGOYSWGFSMQZGMWCCEKGJVLICBXCKCZ454PQ3E46OUVTQ7QC","Remove Num constraint from floorLog"],["2MUXDVSCTYM5RSSP47X2PG7WGCDEUFVGTEG3PJ73PMDPIILUZCYAC","Define subtraction as xor"],["26SW6RDYLEFO6NKSH3TAWMVSMMVEM4E44ODI4T54UOI6ZJV7VAPAC","Use mult' in definition of pow"],["7C7XXN3TSFTJZK4M3BM3T2DJJVB6SCZF7UX42R64ATKVBPIUMWPQC","Add tests for commutativity"],["D53SPHGPFSQ2KE2PLBUZVGEIS2SPFSJRQANHEJ6X3XEBUHJAZHYQC","Use mult' in artinSchreierRoot"],["BKOAQCTL55P6HCIDOLA3WKRDJPPZTFDFROKMKRCLXT7ANA3JG4NQC","Increase test cases"],["V7A5CRSQQY3WTZFNH73E6J4YOKE7YJMEW2XW7YJTM37UNTWRMZJQC","Add Fractional instance and test"],["P63H7XZA5FGJP5RTASK5NOWQDV4BSKFFCN4AIS7RW44KUK3LK2JQC","Add test for square roots"],["M373MXDAPWQZQZT4RWAXFLLUUP5266TW5RUKHB7QNUBUKYQDTOYQC","Use fewer multiplications in recip"],["UJI7ISULWBM24NVDORMLOSCU5VQCCUUYDDKP7WYYMIPGJGOLRI3AC","Use infix operator for xor"],["PMF36FUOINXVVNP5XW6ZOFPPWFBRK62O4VCX45NE4Y4GDPL2Z3BQC","Represent nimbers as natural numbers instead of sets of sets"],["7IBKFG3D35V2UV3JTGM36ZYCF5H3VTLNHAQT24VYKMXQFEJ247IQC","Define signum so that abs x * signum x = x"],["L6TQHWB6JUMHD6KZR3RMO23UHQ2E37P2BAFZGDXBL5KWK2WWAIJQC","Use fewer multiplications in multiplication algorithm"],["WRKY5TH74QSTDAEKIP7NJO4PJVU2HTTYVY7B5OE7VTSRWEOK2J6AC","Add solveQuadratic"],["IKAX7QBJIVJZSXXD6I6UBMPEVPEH3QFNEYGWJKQWMV64IV5U664QC","Use infix operators for shifts"],["6U24OB4HZGUVZZTOEHQKTBOHGV5FKEE4EQDGJF6IP3QQ3HXNNWUQC","Add tests for additive and multiplicative identities"],["VG2W2CCBAB7KY4FSDKB4ZLBRYO763USFRDHUOA3GQOTVNS6XQLSAC","Add test for involutivity"],["ASGE7I4JJ3HTHHSQKVNL74ZVZQ6WTYX6M54FYKOUE4PCPRPUNSUQC","Add Nat type for small natural numbers"],["E6Q5N4UCYKSFJ4YYFRPLOUASOIARTLT2ZU2JJXM3TFP4FICDGAOAC","Remove case from floorLog"],["KARMFRM7OJF6RDDAVRISRV223RS6AWE6BG33QMFJ4GYLQFZYL56QC","Move definitions to test"],["TF6PK6JDRLBRDRJVI7M4RWSJG5NK6SAMSYINXD6ZGSE7DL4ILTMAC","Avoid recomputing log^2"],["WFOLCYCZVNRVCEWSDJR36BGSN6IKJ4CMISYCOWBLENMOP2JUTRIQC","Use faster multiplication algorithm"],["G25ET6HXYNPM2HJ2L76TGOLVV2LBDA3CIWCAN6SL2WKNTUG56RDQC","Use sqr function in definition of recip"],["MCBWM3FBZPTBMBJM4QISAX45C2D75QGHWXPLAYMN3EXJJ2CV4ASAC","Rewrite some functions to avoid recomputing log^2."],["6SEK2PYJEXNK3VPENGSX6W6X23P2KPP6DOQTBUGG2RCVJAU6KKHQC","Add email to cabal file"],["XBKUMBMDBZ37XISOWRJU3QRUUYP3TDT7MO6GYKTLCSTRPESASJTQC","Use a different algorithm for division"],["5CXVNGYMMIBKPFJFJK7T5HLMUAP2IE7UCFZBFZTY5DBJFRQHPP5QC","Move Nimbers.hs to Data.Nimber"],["VRPOSMITS7VRSIJU6YNEBELCUBTHPMPJD6F6F5PE35R2KECS42KAC","Initial commit"],["O6UAIBEXBNE2XMWQWU6YKGGRLDQFI364JMV6HCYCCI3LBQRD6RPQC","Define square roots of nimbers"],["2JT446RMTHP23QL57CULGRWI7A7ATV7HRV2D5FZ4SULIDU5AD4KAC","Add haddock for Num instance"],["XL3UEJW5ODILLWT37VFOTWJG5J4YV4MTODD5BTREEC7ZFSYXQHZQC","Update documentation"],["2Q7SZHYMAFCYLG5MROYQ4BJ7HDIASPLIZJP7SM7BNX4GESUCZXJQC","Add squaring function"],["TEWWDULPAUYV2VFT3LGUTXGVVDPFFTBRHXQVJAZT63D5Q2NLPS6QC","Add power function"]],"deps":["ADE3QH6CJXDMZNXCPR7YTFLUHUV6TFP7Z3V7SMKUELP3JVGCACXQC","73K2ULQWAV2A2MICO4YYOVKX55WJYYHBBQSALBZQBKQJLYIDDPGQC","VZUEVF2UF4O2S3SFZKSV45QBUMQQ5GVNQMYYFU5PXPFX344P7W3QC","CEQIUHRVILZ2JCYTQPEK4LTHSKEZMMS3YXTE3L3ELGMW2RNOH7YQC","3BR6NSGOYSWGFSMQZGMWCCEKGJVLICBXCKCZ454PQ3E46OUVTQ7QC","2MUXDVSCTYM5RSSP47X2PG7WGCDEUFVGTEG3PJ73PMDPIILUZCYAC","26SW6RDYLEFO6NKSH3TAWMVSMMVEM4E44ODI4T54UOI6ZJV7VAPAC","7C7XXN3TSFTJZK4M3BM3T2DJJVB6SCZF7UX42R64ATKVBPIUMWPQC","D53SPHGPFSQ2KE2PLBUZVGEIS2SPFSJRQANHEJ6X3XEBUHJAZHYQC"],"known":["VRPOSMITS7VRSIJU6YNEBELCUBTHPMPJD6F6F5PE35R2KECS42KAC","2JT446RMTHP23QL57CULGRWI7A7ATV7HRV2D5FZ4SULIDU5AD4KAC","V7A5CRSQQY3WTZFNH73E6J4YOKE7YJMEW2XW7YJTM37UNTWRMZJQC","VG2W2CCBAB7KY4FSDKB4ZLBRYO763USFRDHUOA3GQOTVNS6XQLSAC","6U24OB4HZGUVZZTOEHQKTBOHGV5FKEE4EQDGJF6IP3QQ3HXNNWUQC","XBKUMBMDBZ37XISOWRJU3QRUUYP3TDT7MO6GYKTLCSTRPESASJTQC","ASGE7I4JJ3HTHHSQKVNL74ZVZQ6WTYX6M54FYKOUE4PCPRPUNSUQC","PMF36FUOINXVVNP5XW6ZOFPPWFBRK62O4VCX45NE4Y4GDPL2Z3BQC","5CXVNGYMMIBKPFJFJK7T5HLMUAP2IE7UCFZBFZTY5DBJFRQHPP5QC","UJI7ISULWBM24NVDORMLOSCU5VQCCUUYDDKP7WYYMIPGJGOLRI3AC","M373MXDAPWQZQZT4RWAXFLLUUP5266TW5RUKHB7QNUBUKYQDTOYQC","WFOLCYCZVNRVCEWSDJR36BGSN6IKJ4CMISYCOWBLENMOP2JUTRIQC","KARMFRM7OJF6RDDAVRISRV223RS6AWE6BG33QMFJ4GYLQFZYL56QC","BKOAQCTL55P6HCIDOLA3WKRDJPPZTFDFROKMKRCLXT7ANA3JG4NQC","L6TQHWB6JUMHD6KZR3RMO23UHQ2E37P2BAFZGDXBL5KWK2WWAIJQC","O6UAIBEXBNE2XMWQWU6YKGGRLDQFI364JMV6HCYCCI3LBQRD6RPQC","P63H7XZA5FGJP5RTASK5NOWQDV4BSKFFCN4AIS7RW44KUK3LK2JQC","2Q7SZHYMAFCYLG5MROYQ4BJ7HDIASPLIZJP7SM7BNX4GESUCZXJQC","G25ET6HXYNPM2HJ2L76TGOLVV2LBDA3CIWCAN6SL2WKNTUG56RDQC","TEWWDULPAUYV2VFT3LGUTXGVVDPFFTBRHXQVJAZT63D5Q2NLPS6QC","MCBWM3FBZPTBMBJM4QISAX45C2D75QGHWXPLAYMN3EXJJ2CV4ASAC","7IBKFG3D35V2UV3JTGM36ZYCF5H3VTLNHAQT24VYKMXQFEJ247IQC","XL3UEJW5ODILLWT37VFOTWJG5J4YV4MTODD5BTREEC7ZFSYXQHZQC","TF6PK6JDRLBRDRJVI7M4RWSJG5NK6SAMSYINXD6ZGSE7DL4ILTMAC","WRKY5TH74QSTDAEKIP7NJO4PJVU2HTTYVY7B5OE7VTSRWEOK2J6AC","E6Q5N4UCYKSFJ4YYFRPLOUASOIARTLT2ZU2JJXM3TFP4FICDGAOAC","IKAX7QBJIVJZSXXD6I6UBMPEVPEH3QFNEYGWJKQWMV64IV5U664QC","6SEK2PYJEXNK3VPENGSX6W6X23P2KPP6DOQTBUGG2RCVJAU6KKHQC"]},"hunks":[{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":16,"ins":{"up_context":[{"change":11,"pos":184}],"down_context":[{"change":11,"pos":63}],"flag":"BLOCK","start":0,"end":38,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":184},"to":{"change":11,"start":184,"end":216},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"instance Arbitrary FiniteNimber where"}],"del_contents":[{"Del":"instance Arbitrary Nimber where\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":23,"ins":{"up_context":[{"change":11,"pos":257}],"down_context":[{"change":11,"pos":2}],"flag":"BLOCK","start":39,"end":72,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":257},"to":{"change":11,"start":257,"end":284},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_neg :: FiniteNimber -> Bool"}],"del_contents":[{"Del":"prop_neg :: Nimber -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":26,"ins":{"up_context":[{"change":11,"pos":82}],"down_context":[{"change":11,"pos":167}],"flag":"BLOCK","start":73,"end":109,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":82},"to":{"change":11,"start":82,"end":112},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_add_id :: FiniteNimber -> Bool"}],"del_contents":[{"Del":"prop_add_id :: Nimber -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":29,"ins":{"up_context":[{"change":11,"pos":307}],"down_context":[{"change":11,"pos":209}],"flag":"BLOCK","start":110,"end":147,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":307},"to":{"change":11,"start":158,"end":189},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_mult_id :: FiniteNimber -> Bool"}],"del_contents":[{"Del":"prop_mult_id :: Nimber -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":32,"ins":{"up_context":[{"change":9,"pos":3}],"down_context":[{"change":9,"pos":45}],"flag":"BLOCK","start":148,"end":202,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":9,"pos":3},"to":{"change":9,"start":3,"end":45},"introduced_by":9}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_comm_add :: FiniteNimber -> FiniteNimber -> Bool"}],"del_contents":[{"Del":"prop_comm_add :: Nimber -> Nimber -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":35,"ins":{"up_context":[{"change":11,"pos":236}],"down_context":[{"change":9,"pos":124}],"flag":"BLOCK","start":203,"end":258,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":236},"to":{"change":9,"start":81,"end":124},"introduced_by":9}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_comm_mult :: FiniteNimber -> FiniteNimber -> Bool"}],"del_contents":[{"Del":"prop_comm_mult :: Nimber -> Nimber -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":38,"ins":{"up_context":[{"change":9,"pos":161}],"down_context":[{"change":11,"pos":84}],"flag":"BLOCK","start":259,"end":330,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":9,"pos":161},"to":{"change":11,"start":307,"end":360},"introduced_by":9},{"previous":"","flag":"DELETED","from":{"change":11,"pos":236},"to":{"change":11,"start":307,"end":360},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":307},"to":{"change":11,"start":307,"end":360},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_assoc_add :: FiniteNimber -> FiniteNimber -> FiniteNimber -> Bool"}],"del_contents":[{"Del":"prop_assoc_add :: Nimber -> Nimber -> Nimber -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":41,"ins":{"up_context":[{"change":11,"pos":403}],"down_context":[{"change":11,"pos":306}],"flag":"BLOCK","start":331,"end":403,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":403},"to":{"change":11,"start":252,"end":306},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_assoc_mult :: FiniteNimber -> FiniteNimber -> FiniteNimber -> Bool"}],"del_contents":[{"Del":"prop_assoc_mult :: Nimber -> Nimber -> Nimber -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":44,"ins":{"up_context":[{"change":11,"pos":499}],"down_context":[{"change":11,"pos":186}],"flag":"BLOCK","start":404,"end":473,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":499},"to":{"change":11,"start":499,"end":550},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_distrib :: FiniteNimber -> FiniteNimber -> FiniteNimber -> Bool"}],"del_contents":[{"Del":"prop_distrib :: Nimber -> Nimber -> Nimber -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":47,"ins":{"up_context":[{"change":11,"pos":237}],"down_context":[{"change":11,"pos":395}],"flag":"BLOCK","start":474,"end":517,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":237},"to":{"change":11,"start":358,"end":395},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_recip :: NonZero FiniteNimber -> Bool"}],"del_contents":[{"Del":"prop_recip :: NonZero Nimber -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":50,"ins":{"up_context":[{"change":11,"pos":591}],"down_context":[{"change":11,"pos":54}],"flag":"BLOCK","start":518,"end":551,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":591},"to":{"change":11,"start":27,"end":54},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_inv :: FiniteNimber -> Bool"}],"del_contents":[{"Del":"prop_inv :: Nimber -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":53,"ins":{"up_context":[{"change":11,"pos":3}],"down_context":[{"change":11,"pos":2}],"flag":"BLOCK","start":552,"end":585,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":3},"to":{"change":11,"start":109,"end":136},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_sqr :: FiniteNimber -> Bool"}],"del_contents":[{"Del":"prop_sqr :: Nimber -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":56,"ins":{"up_context":[{"change":11,"pos":31}],"down_context":[{"change":11,"pos":77}],"flag":"BLOCK","start":586,"end":638,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":31},"to":{"change":11,"start":31,"end":77},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_pow :: NonZero FiniteNimber -> Integer -> Bool"}],"del_contents":[{"Del":"prop_pow :: NonZero Nimber -> Integer -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":62,"ins":{"up_context":[{"change":11,"pos":46}],"down_context":[{"change":11,"pos":191}],"flag":"BLOCK","start":639,"end":673,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":46},"to":{"change":11,"start":163,"end":191},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_sqrt :: FiniteNimber -> Bool"}],"del_contents":[{"Del":"prop_sqrt :: Nimber -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":65,"ins":{"up_context":[{"change":11,"pos":68}],"down_context":[{"change":11,"pos":471}],"flag":"BLOCK","start":674,"end":706,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":68},"to":{"change":11,"start":445,"end":471},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_as :: FiniteNimber -> Bool"}],"del_contents":[{"Del":"prop_as :: Nimber -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":68,"ins":{"up_context":[{"change":11,"pos":3}],"down_context":[{"change":5,"pos":55}],"flag":"BLOCK","start":707,"end":778,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":3},"to":{"change":5,"start":2,"end":55},"introduced_by":5}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":"prop_quadratic :: FiniteNimber -> FiniteNimber -> FiniteNimber -> Bool"}],"del_contents":[{"Del":"prop_quadratic :: Nimber -> Nimber -> Nimber -> Bool\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":101,"ins":{"up_context":[{"change":11,"pos":937}],"down_context":[{"change":11,"pos":197}],"flag":"BLOCK","start":779,"end":871,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":937},"to":{"change":11,"start":937,"end":1023},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":" pure $ fromIntegral @Int @FiniteNimber (nimberAdd i j) == fromIntegral i + fromIntegral j"}],"del_contents":[{"Del":" pure $ fromIntegral @Int @Nimber (nimberAdd i j) == fromIntegral i + fromIntegral j\n"}]}},{"Replacement":{"inode":{"change":11,"pos":22},"path":"test/Main.hs","line":107,"ins":{"up_context":[{"change":11,"pos":1105}],"down_context":[{"change":11,"pos":965}],"flag":"BLOCK","start":872,"end":965,"inode":{"change":11,"pos":22}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":1105},"to":{"change":11,"start":1105,"end":1192},"introduced_by":11}],"inode":{"change":11,"pos":22}},"ins_contents":[{"Add":" pure $ fromIntegral @Int @FiniteNimber (nimberMult i j) == fromIntegral i * fromIntegral j"}],"del_contents":[{"Del":" pure $ fromIntegral @Int @Nimber (nimberMult i j) == fromIntegral i * fromIntegral j\n"}]}},{"Replacement":{"inode":{"change":11,"pos":880},"path":"src/Data/Nimber.hs","line":1,"ins":{"up_context":[{"change":11,"pos":880}],"down_context":[{"change":11,"pos":388}],"flag":"BLOCK","start":966,"end":1002,"inode":{"change":11,"pos":880}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":880},"to":{"change":11,"start":305,"end":341},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":341},"to":{"change":11,"start":530,"end":570},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":880},"to":{"change":11,"start":530,"end":570},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":570},"to":{"change":11,"start":881,"end":1080},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":880},"to":{"change":11,"start":881,"end":1080},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":1080},"to":{"change":2,"start":4,"end":179},"introduced_by":2},{"previous":"","flag":"DELETED","from":{"change":2,"pos":179},"to":{"change":11,"start":1186,"end":1338},"introduced_by":2},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":1186},"to":{"change":11,"start":1186,"end":1338},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":1338},"to":{"change":11,"start":269,"end":387},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":387},"to":{"change":11,"start":5,"end":96},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":96},"to":{"change":11,"start":168,"end":188},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":188},"to":{"change":11,"start":96,"end":106},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":96},"to":{"change":11,"start":96,"end":106},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":101},"to":{"change":11,"start":4,"end":5},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":106},"to":{"change":11,"start":4,"end":5},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":1521},"to":{"change":11,"start":4,"end":5},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":5},"to":{"change":11,"start":342,"end":359},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":359},"to":{"change":3,"start":5,"end":28},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":28},"to":{"change":11,"start":1521,"end":1522},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":11,"pos":48},"to":{"change":11,"start":1521,"end":1522},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":359},"to":{"change":11,"start":1521,"end":1522},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":686},"to":{"change":11,"start":1521,"end":1522},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":1521},"to":{"change":11,"start":1521,"end":1522},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2147},"to":{"change":11,"start":360,"end":454},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":454},"to":{"change":11,"start":2455,"end":2456},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2455},"to":{"change":11,"start":2455,"end":2456},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2456},"to":{"change":11,"start":107,"end":169},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":169},"to":{"change":6,"start":5,"end":117},"introduced_by":6},{"previous":"","flag":"DELETED","from":{"change":11,"pos":42},"to":{"change":11,"start":2740,"end":2741},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":6,"pos":117},"to":{"change":11,"start":2740,"end":2741},"introduced_by":6},{"previous":"","flag":"DELETED","from":{"change":11,"pos":744},"to":{"change":11,"start":2740,"end":2741},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2740},"to":{"change":11,"start":2740,"end":2741},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2741},"to":{"change":11,"start":187,"end":359},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":359},"to":{"change":11,"start":43,"end":185},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":185},"to":{"change":11,"start":517,"end":547},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":517},"to":{"change":11,"start":517,"end":547},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":547},"to":{"change":11,"start":186,"end":293},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":293},"to":{"change":11,"start":658,"end":659},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":658},"to":{"change":11,"start":658,"end":659},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":659},"to":{"change":11,"start":5,"end":182},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2741},"to":{"change":11,"start":5,"end":182},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":182},"to":{"change":11,"start":176,"end":179},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":176},"to":{"change":11,"start":176,"end":179},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":179},"to":{"change":11,"start":183,"end":397},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":397},"to":{"change":11,"start":388,"end":504},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":388},"to":{"change":11,"start":388,"end":504},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":69},"to":{"change":11,"start":2741,"end":2767},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":605},"to":{"change":11,"start":2741,"end":2767},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2741},"to":{"change":11,"start":2741,"end":2767},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2767},"to":{"change":11,"start":745,"end":801},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":801},"to":{"change":7,"start":5,"end":17},"introduced_by":7},{"previous":"","flag":"DELETED","from":{"change":7,"pos":17},"to":{"change":11,"start":49,"end":211},"introduced_by":7},{"previous":"","flag":"DELETED","from":{"change":11,"pos":29},"to":{"change":11,"start":49,"end":211},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":49},"to":{"change":11,"start":49,"end":211},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":1712},"to":{"change":11,"start":1712,"end":1732},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":125},"to":{"change":11,"start":3728,"end":3753},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":501},"to":{"change":11,"start":3728,"end":3753},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":1732},"to":{"change":11,"start":3728,"end":3753},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":3728},"to":{"change":11,"start":3728,"end":3753},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":3753},"to":{"change":11,"start":70,"end":100},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":100},"to":{"change":11,"start":738,"end":739},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":738},"to":{"change":11,"start":738,"end":739},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":739},"to":{"change":11,"start":660,"end":729},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":729},"to":{"change":11,"start":294,"end":353},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":353},"to":{"change":11,"start":796,"end":866},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":796},"to":{"change":11,"start":796,"end":866},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":866},"to":{"change":11,"start":5,"end":38},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":38},"to":{"change":11,"start":354,"end":416},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":104},"to":{"change":11,"start":964,"end":965},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":416},"to":{"change":11,"start":964,"end":965},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":964},"to":{"change":11,"start":964,"end":965},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":965},"to":{"change":11,"start":739,"end":827},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":739},"to":{"change":11,"start":739,"end":827},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":847},"to":{"change":11,"start":847,"end":959},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2047},"to":{"change":11,"start":2047,"end":2062},"introduced_by":11}],"inode":{"change":11,"pos":880}},"ins_contents":[{"Add":"module Data.Nimber (module M) where"}],"del_contents":[{"Del":"{-# LANGUAGE DerivingStrategies #-}\n"},{"Del":"{-# OPTIONS_GHC -Wno-type-defaults #-}\n\n"},{"Del":"-- | In combinatorial game theory, nimbers represent the values of impartial games. They are the simplest way of making the ordinals into a Field.\n-- See /On Numbers and Games/ by John Conway.\n--\n"},{"Del":"-- Nimber addition is defined by \$\\alpha+\\beta = \\operatorname{mex}\\{\\alpha'+\\beta, \\alpha+\\beta'\\}\$, where \$\\operatorname{mex} S\$ is the smallest ordinal not in \$S\$.\n"},{"Del":"--\n-- Nimber multiplication is defined by \$\\alpha\\cdot\\beta = \\operatorname{mex}\\{\\alpha'\\cdot\\beta + \\alpha\\cdot\\beta' - \\alpha'\\cdot\\beta'\\}\$.\n--\n"},{"Del":"-- This module implements /finite/ nimbers, which form the smallest quadratically closed field of characteristic 2.\n"},{"Del":"module Data.Nimber\n ( Nimber (..),\n floorLog,\n sqr,\n pow,\n artinSchreierRoot,\n"},{"Del":" solveQuadratic,\n"},{"Del":" )\nwhere\n"},{"Del":"\n"},{"Del":"import Data.Bits\n"},{"Del":"import Numeric.Natural\n"},{"Del":"\n"},{"Del":"newtype Nimber = Nimber {getNimber :: Natural}\n deriving newtype (Show, Eq, Ord, Enum, Bits)\n"},{"Del":"\n"},{"Del":"-- | Index of highest-order set bit, or -1 if there are none.\n"},{"Del":"floorLog :: (Bits a, Num b) => a -> b\nfloorLog n\n | n == zeroBits = -1\n | otherwise = 1 + floorLog (n .>>. 1)\n"},{"Del":"\n"},{"Del":"mult' :: Int -> Nimber -> Nimber -> Nimber\nmult' _ 0 _ = 0\nmult' _ _ 0 = 0\nmult' _ 1 b = b\nmult' _ a 1 = a\nmult' m a b =\n let semiD = bit (bit m - 1) -- semimultiple of D\n"},{"Del":" s1 = a .>>. bit m -- a = a1D+a2\n s2 = a .^. (s1 .<<. bit m)\n t1 = b .>>. bit m -- b = b1D+b2\n t2 = b .^. (t1 .<<. bit m)\n"},{"Del":" c = mult' (m - 1) s2 t2\n"},{"Del":" in ((mult' (m - 1) (s1 + s2) (t1 + t2) - c) .<<. bit m) + mult' (m - 1) (mult' (m - 1) s1 t1) semiD + c\n"},{"Del":"\n"},{"Del":"-- | Finite nimber addition is calculated as follows: the nimber sum of a two-power and itself is 0, while the nimber sum of a set of distinct two-powers is their ordinary sum.\n"},{"Del":"--\n"},{"Del":"-- Finite nimber multiplication is calculated as follows: the nimber square of a Fermat two-power is its sesquimultiple, while the nimber product of a set of distinct Fermat two-powers is their ordinary product.\n"},{"Del":"-- The sesquimultiple of a Fermat two-power is equal to itself plus the product of all smaller Fermat two-powers.\n"},{"Del":"instance Num Nimber where\n"},{"Del":" fromInteger = Nimber . fromIntegral . abs\n (+) = xor\n"},{"Del":" (-) = xor\n"},{"Del":" a * b =\n let m = max (floorLog @Int (floorLog a)) (floorLog @Int (floorLog b)) -- D = 2^2^m is the largest Fermat 2-power less than or equal to both a and b\n"},{"Del":" in mult' m a b\n"},{"Del":" negate = id\n abs = id\n"},{"Del":" signum 0 = 0\n signum _ = 1\n"},{"Del":"\n"},{"Del":"sqr' :: Int -> Nimber -> Nimber\nsqr' _ 0 = 0\nsqr' _ 1 = 1\nsqr' m n =\n"},{"Del":" let a = n .>>. bit m -- n = aD+b\n aD = a .<<. bit m\n"},{"Del":" b = n .^. aD\n semiD = bit (bit m - 1) -- semimultiple of D\n"},{"Del":" a2 = sqr' (m - 1) a -- a^2\n"},{"Del":" in a2 .<<. bit m + mult' (m - 1) a2 semiD + sqr' (m - 1) b\n"},{"Del":"\n"},{"Del":"-- | Squaring function. Faster than multiplying @n@ by itself.\nsqr :: Nimber -> Nimber\n"},{"Del":"sqr n =\n let m = floorLog @Int $ floorLog n -- D = 2^2^m is the largest Fermat 2-power less than or equal to n\n"},{"Del":" in sqr' m n\n"}]}},{"Replacement":{"inode":{"change":11,"pos":880},"path":"src/Data/Nimber.hs","line":3,"ins":{"up_context":[{"change":11,"pos":389}],"down_context":[],"flag":"BLOCK","start":1003,"end":1034,"inode":{"change":11,"pos":880}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":389},"to":{"change":11,"start":389,"end":467},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":467},"to":{"change":11,"start":2063,"end":2161},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2161},"to":{"change":11,"start":966,"end":1023},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":1023},"to":{"change":8,"start":5,"end":132},"introduced_by":8},{"previous":"","flag":"DELETED","from":{"change":8,"pos":132},"to":{"change":11,"start":5,"end":6},"introduced_by":8},{"previous":"","flag":"DELETED","from":{"change":11,"pos":786},"to":{"change":11,"start":5,"end":6},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":1143},"to":{"change":11,"start":5,"end":6},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":1164},"to":{"change":11,"start":5,"end":6},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":2282},"to":{"change":11,"start":5,"end":6},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":58},"to":{"change":11,"start":5,"end":6},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":6},"to":{"change":11,"start":5,"end":291},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":340},"to":{"change":11,"start":340,"end":458},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":458},"to":{"change":11,"start":1144,"end":1188},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":1188},"to":{"change":11,"start":2283,"end":2327},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":458},"to":{"change":11,"start":2283,"end":2327},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2327},"to":{"change":11,"start":417,"end":492},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":492},"to":{"change":11,"start":2410,"end":2496},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2410},"to":{"change":11,"start":2410,"end":2496},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2496},"to":{"change":4,"start":5,"end":117},"introduced_by":4},{"previous":"","flag":"DELETED","from":{"change":4,"pos":117},"to":{"change":11,"start":2570,"end":2589},"introduced_by":4},{"previous":"","flag":"DELETED","from":{"change":11,"pos":1306},"to":{"change":11,"start":2570,"end":2589},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2570},"to":{"change":11,"start":2570,"end":2589},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":2589},"to":{"change":11,"start":656,"end":657},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":656},"to":{"change":11,"start":656,"end":657},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":657},"to":{"change":11,"start":6,"end":168},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":6},"to":{"change":11,"start":6,"end":168},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":194},"to":{"change":11,"start":194,"end":311},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":311},"to":{"change":11,"start":2590,"end":2654},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2654},"to":{"change":11,"start":493,"end":568},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":568},"to":{"change":11,"start":2737,"end":2764},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2737},"to":{"change":11,"start":2737,"end":2764},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2764},"to":{"change":7,"start":18,"end":77},"introduced_by":7},{"previous":"","flag":"DELETED","from":{"change":7,"pos":77},"to":{"change":11,"start":2823,"end":2861},"introduced_by":7},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2823},"to":{"change":11,"start":2823,"end":2861},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2861},"to":{"change":11,"start":569,"end":662},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":662},"to":{"change":11,"start":2935,"end":2953},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":1404},"to":{"change":11,"start":2935,"end":2953},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":2935},"to":{"change":11,"start":2935,"end":2953},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":1247},"to":{"change":11,"start":517,"end":1401},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":2953},"to":{"change":11,"start":517,"end":1401},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":517},"to":{"change":11,"start":517,"end":1401},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":1401},"to":{"change":11,"start":2954,"end":3819},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":3819},"to":{"change":11,"start":1405,"end":1440},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":1440},"to":{"change":11,"start":3849,"end":3878},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":3849},"to":{"change":11,"start":3849,"end":3878},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":3878},"to":{"change":11,"start":1441,"end":1556},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":1556},"to":{"change":11,"start":3981,"end":4111},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":3981},"to":{"change":11,"start":3981,"end":4111},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":4111},"to":{"change":11,"start":1557,"end":1666},"introduced_by":11},{"previous":"","flag":"DELETED","from":{"change":11,"pos":1666},"to":{"change":11,"start":4213,"end":4289},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":4213},"to":{"change":11,"start":4213,"end":4289},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":4289},"to":{"change":10,"start":5,"end":160},"introduced_by":10},{"previous":"","flag":"DELETED","from":{"change":10,"pos":160},"to":{"change":11,"start":4418,"end":4538},"introduced_by":10},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":4418},"to":{"change":11,"start":4418,"end":4538},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":4538},"to":{"change":11,"start":189,"end":371},"introduced_by":11},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":371},"to":{"change":5,"start":151,"end":248},"introduced_by":5}],"inode":{"change":11,"pos":880}},"ins_contents":[{"Add":"import Data.Nimber.Finite as M"}],"del_contents":[{"Del":"-- | Raise a @'Nimber'@ to an integral power. Faster than using '^' or '^^'.\n"},{"Del":"pow :: (Integral a, Bits a) => Nimber -> a -> Nimber\nx `pow` n\n | n < 0 = recip x `pow` negate n\n"},{"Del":" | otherwise =\n let m = floorLog @Int $ floorLog x\n"},{"Del":" in (foldr (mult' m . snd) 1 . filter (testBit n . fst) . zip [0 ..] . take (1 + floorLog (n + 1))) $ iterate (sqr' m) x\n"},{"Del":"\n"},{"Del":"-- | The finite nimbers are a field of characteristic 2. There is no field homomorphism from the rationals to the nimbers, so @'fromRational'@ is always an error.\ninstance Fractional Nimber where\n fromRational _ = error \"Cannot map from field of characteristic 0 to characteristic 2\"\n"},{"Del":" recip n =\n let m = floorLog @Int $ floorLog n -- D = 2^2^m is the largest Fermat 2-power less than or equal to n\n"},{"Del":" recip' _ 0 = error \"Divide by zero\"\n"},{"Del":" recip' _ 1 = 1\n recip' k l =\n"},{"Del":" let a = l .>>. bit k -- n = aD+b\n aD = a .<<. bit k\n"},{"Del":" b = l .^. aD\n semiD = bit (bit k - 1) -- semimultiple of D\n"},{"Del":" in mult' k (l + a) $ recip' (k - 1) (mult' (k - 1) semiD (sqr' (k - 1) a) + mult' (k - 1) b (a + b))\n"},{"Del":" in recip' m n\n"},{"Del":"\n"},{"Del":"-- | The only reason this instance exists is to define square roots. None of the other @'Floating'@ methods apply to @'Nimber'@s.\ninstance Floating Nimber where\n"},{"Del":" sqrt n =\n let m = floorLog @Int $ floorLog n -- D = 2^2^m is the largest Fermat 2-power less than or equal to n\n"},{"Del":" sqrt' _ 0 = 0\n sqrt' _ 1 = 1\n sqrt' k l =\n"},{"Del":" let a = l .>>. bit k -- n = aD+b\n aD = a .<<. bit k\n"},{"Del":" b = l .^. aD\n"},{"Del":" semiD = bit $ bit k - 1 -- semimultiple of D\n"},{"Del":" sqrta = sqrt' (k - 1) a\n"},{"Del":" in sqrta .<<. bit k + mult' (k - 1) sqrta (sqrt' (k - 1) semiD) + sqrt' (k - 1) b\n"},{"Del":" in sqrt' m n\n"},{"Del":" pi = error \"π is not a nimber\"\n exp _ = error \"exp undefined for nimbers\"\n log _ = error \"log undefined for nimbers\"\n sin _ = error \"Trigonometric functions undefined for nimbers\"\n cos _ = error \"Trigonometric functions undefined for nimbers\"\n tan _ = error \"Trigonometric functions undefined for nimbers\"\n asin _ = error \"Trigonometric functions undefined for nimbers\"\n acos _ = error \"Trigonometric functions undefined for nimbers\"\n atan _ = error \"Trigonometric functions undefined for nimbers\"\n sinh _ = error \"Hyperbolic functions undefined for nimbers\"\n cosh _ = error \"Hyperbolic functions undefined for nimbers\"\n tanh _ = error \"Hyperbolic functions undefined for nimbers\"\n asinh _ = error \"Hyperbolic functions undefined for nimbers\"\n acosh _ = error \"Hyperbolic functions undefined for nimbers\"\n atanh _ = error \"Hyperbolic functions undefined for nimbers\"\n"},{"Del":"\nevens :: [a] -> [a]\nevens (x : _ : xs) = x : evens xs\nevens xs = xs\n\n-- | @'artinSchreierRoot' n@ is the smallest solution to the equation \$x^2 - x = n\$.\n-- The algorithm is due to Chin-Long Chen: .\n-- In fields of characteristic 2, the standard quadratic formula does not work, but any quadratic equation can be solved using square roots and Artin-Schreier roots.\n--\n-- This function is __much__ slower than @'sqrt'@.\nartinSchreierRoot :: Nimber -> Nimber\nartinSchreierRoot 0 = 0\nartinSchreierRoot 1 = 2\nartinSchreierRoot 2 = 4\nartinSchreierRoot 3 = 6\nartinSchreierRoot n =\n let m = 1 + floorLog @Int (floorLog n) -- 2^2^m is the order of the smallest field containing n\n m' = if n < bit (bit m - 1) then m else m + 1 -- 2^2^m' is the order of the smallest field containing the Artin-Schreier root of n\n"},{"Del":" squares = iterate (sqr' m) n\n"},{"Del":" quarts = evens squares\n"},{"Del":" semiTrace = sum $ take (bit (m' - 1)) quarts -- trace of the Artin-Screier root of n\n in if semiTrace == 1\n"},{"Del":" then\n let s = sum $ do\n j <- [1 .. bit (m' - 2) - 1]\n i <- [j .. bit (m' - 2) - 1]\n"},{"Del":" pure $ mult' m' (squares !! (shiftL i 1 - 1 .^. bit (m' - 1))) (squares !! (shiftL j 1 - 2))\n"},{"Del":" in flip clearBit 0 $\n s\n + sqr s\n"},{"Del":" + mult' m\n (squares !! (bit m' - 1))\n (1 + sum (take (bit (m' - 2)) $ drop (bit (m' - 2)) quarts))\n"},{"Del":" else\n let y = bit $ bit m' - 1\n z = artinSchreierRoot $ sqr y + y + n\n in y + z\n"},{"Del":"\n-- | @'solveQuadratic' p q@ returns the solutions to the equation \$X^2 + px + q = 0\$.\nsolveQuadratic :: Nimber -> Nimber -> (Nimber, Nimber)\nsolveQuadratic 0 q = (sqrt q, sqrt q)\n"},{"Del":"solveQuadratic p q = let x = p * artinSchreierRoot (q / sqr p) in (min x $ x + p, max x $ x + p)\n"}]}},{"FileAdd":{"meta":{"basename":"Nimber","metadata":576},"context":[{"change":11,"pos":24}],"contents":[]}},{"FileAdd":{"meta":{"basename":"Finite.hs","metadata":0},"context":[{"change":0,"pos":1053}],"contents":[{"Add":"{-# LANGUAGE DerivingStrategies #-}"},{"Add":"{-# OPTIONS_GHC -Wno-type-defaults #-}"},{"Add":""},{"Add":"-- | In combinatorial game theory, nimbers represent the values of impartial games. They are the simplest way of making the ordinals into a Field."},{"Add":"-- See /On Numbers and Games/ by John Conway."},{"Add":"--"},{"Add":"-- Nimber addition is defined by \$\\alpha+\\beta = \\operatorname{mex}\\{\\alpha'+\\beta, \\alpha+\\beta'\\}\$, where \$\\operatorname{mex} S\$ is the smallest ordinal not in \$S\$."},{"Add":"--"},{"Add":"-- Nimber multiplication is defined by \$\\alpha\\cdot\\beta = \\operatorname{mex}\\{\\alpha'\\cdot\\beta + \\alpha\\cdot\\beta' - \\alpha'\\cdot\\beta'\\}\$."},{"Add":"--"},{"Add":"-- This module implements /finite/ nimbers, which form the smallest quadratically closed field of characteristic 2."},{"Add":"module Data.Nimber.Finite"},{"Add":" ( FiniteNimber (..),"},{"Add":" floorLog,"},{"Add":" sqr,"},{"Add":" pow,"},{"Add":" artinSchreierRoot,"},{"Add":" solveQuadratic,"},{"Add":" )"},{"Add":"where"},{"Add":""},{"Add":"import Data.Bits"},{"Add":"import Numeric.Natural"},{"Add":""},{"Add":"newtype FiniteNimber = FiniteNimber {getFiniteNimber :: Natural}"},{"Add":" deriving newtype (Show, Eq, Ord, Enum, Bits)"},{"Add":""},{"Add":"-- | Index of highest-order set bit, or -1 if there are none."},{"Add":"floorLog :: (Bits a, Num b) => a -> b"},{"Add":"floorLog n"},{"Add":" | n == zeroBits = -1"},{"Add":" | otherwise = 1 + floorLog (n .>>. 1)"},{"Add":""},{"Add":"mult' :: Int -> FiniteNimber -> FiniteNimber -> FiniteNimber"},{"Add":"mult' _ 0 _ = 0"},{"Add":"mult' _ _ 0 = 0"},{"Add":"mult' _ 1 b = b"},{"Add":"mult' _ a 1 = a"},{"Add":"mult' m a b ="},{"Add":" let semiD = bit (bit m - 1) -- semimultiple of D"},{"Add":" s1 = a .>>. bit m -- a = a1D+a2"},{"Add":" s2 = a .^. (s1 .<<. bit m)"},{"Add":" t1 = b .>>. bit m -- b = b1D+b2"},{"Add":" t2 = b .^. (t1 .<<. bit m)"},{"Add":" c = mult' (m - 1) s2 t2"},{"Add":" in ((mult' (m - 1) (s1 + s2) (t1 + t2) - c) .<<. bit m) + mult' (m - 1) (mult' (m - 1) s1 t1) semiD + c"},{"Add":""},{"Add":"-- | Finite nimber addition is calculated as follows: the nimber sum of a two-power and itself is 0, while the nimber sum of a set of distinct two-powers is their ordinary sum."},{"Add":"--"},{"Add":"-- Finite nimber multiplication is calculated as follows: the nimber square of a Fermat two-power is its sesquimultiple, while the nimber product of a set of distinct Fermat two-powers is their ordinary product."},{"Add":"-- The sesquimultiple of a Fermat two-power is equal to itself plus the product of all smaller Fermat two-powers."},{"Add":"instance Num FiniteNimber where"},{"Add":" fromInteger = FiniteNimber . fromIntegral . abs"},{"Add":" (+) = xor"},{"Add":" (-) = xor"},{"Add":" a * b ="},{"Add":" let m = max (floorLog @Int (floorLog a)) (floorLog @Int (floorLog b)) -- D = 2^2^m is the largest Fermat 2-power less than or equal to both a and b"},{"Add":" in mult' m a b"},{"Add":" negate = id"},{"Add":" abs = id"},{"Add":" signum 0 = 0"},{"Add":" signum _ = 1"},{"Add":""},{"Add":"sqr' :: Int -> FiniteNimber -> FiniteNimber"},{"Add":"sqr' _ 0 = 0"},{"Add":"sqr' _ 1 = 1"},{"Add":"sqr' m n ="},{"Add":" let a = n .>>. bit m -- n = aD+b"},{"Add":" aD = a .<<. bit m"},{"Add":" b = n .^. aD"},{"Add":" semiD = bit (bit m - 1) -- semimultiple of D"},{"Add":" a2 = sqr' (m - 1) a -- a^2"},{"Add":" in a2 .<<. bit m + mult' (m - 1) a2 semiD + sqr' (m - 1) b"},{"Add":""},{"Add":"-- | Squaring function. Faster than multiplying @n@ by itself."},{"Add":"sqr :: FiniteNimber -> FiniteNimber"},{"Add":"sqr n ="},{"Add":" let m = floorLog @Int $ floorLog n -- D = 2^2^m is the largest Fermat 2-power less than or equal to n"},{"Add":" in sqr' m n"},{"Add":""},{"Add":"-- | Raise a @'FiniteNimber'@ to an integral power. Faster than using '^' or '^^'."},{"Add":"pow :: (Integral a, Bits a) => FiniteNimber -> a -> FiniteNimber"},{"Add":"x `pow` n"},{"Add":" | n < 0 = recip x `pow` negate n"},{"Add":" | otherwise ="},{"Add":" let m = floorLog @Int $ floorLog x"},{"Add":" in (foldr (mult' m . snd) 1 . filter (testBit n . fst) . zip [0 ..] . take (1 + floorLog (n + 1))) $ iterate (sqr' m) x"},{"Add":""},{"Add":"-- | The finite nimbers are a field of characteristic 2. There is no field homomorphism from the rationals to the nimbers, so @'fromRational'@ is always an error."},{"Add":"instance Fractional FiniteNimber where"},{"Add":" fromRational _ = error \"Cannot map from field of characteristic 0 to characteristic 2\""},{"Add":" recip n ="},{"Add":" let m = floorLog @Int $ floorLog n -- D = 2^2^m is the largest Fermat 2-power less than or equal to n"},{"Add":" recip' _ 0 = error \"Divide by zero\""},{"Add":" recip' _ 1 = 1"},{"Add":" recip' k l ="},{"Add":" let a = l .>>. bit k -- n = aD+b"},{"Add":" aD = a .<<. bit k"},{"Add":" b = l .^. aD"},{"Add":" semiD = bit (bit k - 1) -- semimultiple of D"},{"Add":" in mult' k (l + a) $ recip' (k - 1) (mult' (k - 1) semiD (sqr' (k - 1) a) + mult' (k - 1) b (a + b))"},{"Add":" in recip' m n"},{"Add":""},{"Add":"-- | The only reason this instance exists is to define square roots. None of the other @'Floating'@ methods apply to @'FiniteNimber'@s."},{"Add":"instance Floating FiniteNimber where"},{"Add":" sqrt n ="},{"Add":" let m = floorLog @Int $ floorLog n -- D = 2^2^m is the largest Fermat 2-power less than or equal to n"},{"Add":" sqrt' _ 0 = 0"},{"Add":" sqrt' _ 1 = 1"},{"Add":" sqrt' k l ="},{"Add":" let a = l .>>. bit k -- n = aD+b"},{"Add":" aD = a .<<. bit k"},{"Add":" b = l .^. aD"},{"Add":" semiD = bit $ bit k - 1 -- semimultiple of D"},{"Add":" sqrta = sqrt' (k - 1) a"},{"Add":" in sqrta .<<. bit k + mult' (k - 1) sqrta (sqrt' (k - 1) semiD) + sqrt' (k - 1) b"},{"Add":" in sqrt' m n"},{"Add":" pi = error \"π is not a nimber\""},{"Add":" exp _ = error \"exp undefined for nimbers\""},{"Add":" log _ = error \"log undefined for nimbers\""},{"Add":" sin _ = error \"Trigonometric functions undefined for nimbers\""},{"Add":" cos _ = error \"Trigonometric functions undefined for nimbers\""},{"Add":" tan _ = error \"Trigonometric functions undefined for nimbers\""},{"Add":" asin _ = error \"Trigonometric functions undefined for nimbers\""},{"Add":" acos _ = error \"Trigonometric functions undefined for nimbers\""},{"Add":" atan _ = error \"Trigonometric functions undefined for nimbers\""},{"Add":" sinh _ = error \"Hyperbolic functions undefined for nimbers\""},{"Add":" cosh _ = error \"Hyperbolic functions undefined for nimbers\""},{"Add":" tanh _ = error \"Hyperbolic functions undefined for nimbers\""},{"Add":" asinh _ = error \"Hyperbolic functions undefined for nimbers\""},{"Add":" acosh _ = error \"Hyperbolic functions undefined for nimbers\""},{"Add":" atanh _ = error \"Hyperbolic functions undefined for nimbers\""},{"Add":""},{"Add":"evens :: [a] -> [a]"},{"Add":"evens (x : _ : xs) = x : evens xs"},{"Add":"evens xs = xs"},{"Add":""},{"Add":"-- | @'artinSchreierRoot' n@ is the smallest solution to the equation \$x^2 - x = n\$."},{"Add":"-- The algorithm is due to Chin-Long Chen: ."},{"Add":"-- In fields of characteristic 2, the standard quadratic formula does not work, but any quadratic equation can be solved using square roots and Artin-Schreier roots."},{"Add":"--"},{"Add":"-- This function is __much__ slower than @'sqrt'@."},{"Add":"artinSchreierRoot :: FiniteNimber -> FiniteNimber"},{"Add":"artinSchreierRoot 0 = 0"},{"Add":"artinSchreierRoot 1 = 2"},{"Add":"artinSchreierRoot 2 = 4"},{"Add":"artinSchreierRoot 3 = 6"},{"Add":"artinSchreierRoot n ="},{"Add":" let m = 1 + floorLog @Int (floorLog n) -- 2^2^m is the order of the smallest field containing n"},{"Add":" m' = if n < bit (bit m - 1) then m else m + 1 -- 2^2^m' is the order of the smallest field containing the Artin-Schreier root of n"},{"Add":" squares = iterate (sqr' m) n"},{"Add":" quarts = evens squares"},{"Add":" semiTrace = sum $ take (bit (m' - 1)) quarts -- trace of the Artin-Screier root of n"},{"Add":" in if semiTrace == 1"},{"Add":" then"},{"Add":" let s = sum $ do"},{"Add":" j <- [1 .. bit (m' - 2) - 1]"},{"Add":" i <- [j .. bit (m' - 2) - 1]"},{"Add":" pure $ mult' m' (squares !! (shiftL i 1 - 1 .^. bit (m' - 1))) (squares !! (shiftL j 1 - 2))"},{"Add":" in flip clearBit 0 $"},{"Add":" s"},{"Add":" + sqr s"},{"Add":" + mult' m"},{"Add":" (squares !! (bit m' - 1))"},{"Add":" (1 + sum (take (bit (m' - 2)) $ drop (bit (m' - 2)) quarts))"},{"Add":" else"},{"Add":" let y = bit $ bit m' - 1"},{"Add":" z = artinSchreierRoot $ sqr y + y + n"},{"Add":" in y + z"},{"Add":""},{"Add":"-- | @'solveQuadratic' p q@ returns the solutions to the equation \$X^2 + px + q = 0\$."},{"Add":"solveQuadratic :: FiniteNimber -> FiniteNimber -> (FiniteNimber, FiniteNimber)"},{"Add":"solveQuadratic 0 q = (sqrt q, sqrt q)"},{"Add":"solveQuadratic p q = let x = p * artinSchreierRoot (q / sqr p) in (min x $ x + p, max x $ x + p)"}]}},{"Replacement":{"inode":{"change":11,"pos":4726},"path":"nimbers.cabal","line":62,"ins":{"up_context":[{"change":11,"pos":6709}],"down_context":[{"change":11,"pos":6739}],"flag":"BLOCK","start":8801,"end":8877,"inode":{"change":11,"pos":4726}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":11,"pos":6709},"to":{"change":11,"start":103,"end":137},"introduced_by":11}],"inode":{"change":11,"pos":4726}},"ins_contents":[{"Add":" exposed-modules: Data.Nimber,"},{"Add":" Data.Nimber.Finite"}],"del_contents":[{"Del":" exposed-modules: Data.Nimber\n"}]}}],"owner":"noiioiu","repo":"nimbers","token":"eOHmyfBtp8b0sM61VqbDME/xZ/rTvK/bqqHjqhUYv4o=","login":null}

…

Dependencies

Change contents