aboutsummaryrefslogtreecommitdiff
path: root/src/Arithmetic
Commit message (Collapse)AuthorAge
* Backwards compatible fix for some issues from ↵Gravatar Jason Gross2018-08-04
| | | | https://github.com/coq/coq/pull/8200
* Make Z.div_mod_to_quot_rem strongerGravatar Jason Gross2018-07-10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | It now handles things in the context by default, and also handles cases where we don't have non-zero hypotheses. We change existing uses of Z.div_mod_to_quot_rem to Z.div_mod_to_quot_rem_in_goal to minimize changes in behavior/timing; new proofs should use Z.div_mod_to_quot_rem. After | File Name | Before || Change | % Change ------------------------------------------------------------------------------------------------------------------- 65m52.33s | Total | 65m20.46s || +0m31.86s | +0.81% ------------------------------------------------------------------------------------------------------------------- N/A | Specific/X25519/C64/freeze | 0m24.36s || -0m24.35s | -100.00% 0m24.28s | ─abstract | N/A || +0m24.28s | ∞ 9m54.51s | Experiments/SimplyTypedArithmetic | 9m31.70s || +0m22.80s | +3.98% 1m01.94s | Compilers/Z/ArithmeticSimplifierInterp | 0m52.32s || +0m09.61s | +18.38% 4m58.61s | Curves/Montgomery/XZProofs | 4m52.72s || +0m05.88s | +2.01% 1m27.64s | Experiments/NewPipeline/Arithmetic | 1m22.31s || +0m05.32s | +6.47% 0m50.26s | Specific/X25519/C32/freeze | 0m55.45s || -0m05.19s | -9.35% 0m57.78s | Arithmetic/Karatsuba | 1m02.08s || -0m04.29s | -6.92% 0m30.88s | Specific/NISTP256/AMD64/feadd | 0m26.45s || +0m04.42s | +16.74% 1m42.40s | Spec/Test/X25519 | 1m45.72s || -0m03.31s | -3.14% 1m15.70s | Demo | 1m19.38s || -0m03.67s | -4.63% 1m10.46s | Compilers/Z/Named/RewriteAddToAdcInterp | 1m13.62s || -0m03.15s | -4.29% 1m01.68s | Specific/X25519/C32/fesquare | 1m05.12s || -0m03.44s | -5.28% 0m40.98s | Spec/Ed25519 | 0m44.17s || -0m03.19s | -7.22% 0m30.06s | Specific/NISTP256/AMD64/fesub | 0m33.28s || -0m03.22s | -9.67% 0m27.69s | Specific/X25519/C32/feadd | 0m30.70s || -0m03.00s | -9.80% 0m22.12s | Specific/X25519/C64/fesub | 0m19.02s || +0m03.10s | +16.29% 0m19.61s | Specific/X25519/C64/fecarry | 0m22.71s || -0m03.10s | -13.65% 2m24.22s | Specific/NISTP256/AMD64/femul | 2m21.54s || +0m02.68s | +1.89% 1m52.74s | Compilers/Named/MapCastInterp | 1m55.32s || -0m02.57s | -2.23% 1m49.40s | Specific/X2448/Karatsuba/C64/femul | 1m46.44s || +0m02.96s | +2.78% 1m26.20s | Specific/X25519/C32/femul | 1m23.74s || +0m02.46s | +2.93% 0m22.70s | Specific/NISTP256/AMD128/feadd | 0m20.55s || +0m02.14s | +10.46% 0m18.83s | Arithmetic/Saturated/AddSub | 0m20.85s || -0m02.02s | -9.68% 0m17.20s | Specific/X25519/C64/feadd | 0m19.71s || -0m02.51s | -12.73% 0m11.89s | LegacyArithmetic/Double/Proofs/SpreadLeftImmediate | 0m09.75s || +0m02.14s | +21.94% 6m49.81s | Experiments/NewPipeline/SlowPrimeSynthesisExamples | 6m51.21s || -0m01.39s | -0.34% 2m18.78s | Experiments/NewPipeline/Toplevel1 | 2m17.03s || +0m01.75s | +1.27% 2m17.99s | Specific/X25519/C64/ladderstep | 2m16.16s || +0m01.83s | +1.34% 0m45.70s | Specific/NISTP256/AMD128/femul | 0m44.04s || +0m01.66s | +3.76% 0m40.77s | Specific/X25519/C32/fecarry | 0m39.11s || +0m01.66s | +4.24% 0m32.96s | Arithmetic/Core | 0m31.64s || +0m01.32s | +4.17% 0m26.76s | Specific/X25519/C64/fesquare | 0m25.41s || +0m01.35s | +5.31% 0m24.35s | Specific/NISTP256/AMD64/feopp | 0m25.98s || -0m01.62s | -6.27% 0m20.48s | Specific/NISTP256/AMD64/fenz | 0m19.46s || +0m01.01s | +5.24% 0m18.82s | Specific/NISTP256/AMD128/fenz | 0m20.44s || -0m01.62s | -7.92% 0m15.83s | Arithmetic/MontgomeryReduction/Proofs | 0m14.14s || +0m01.68s | +11.95% 0m14.68s | LegacyArithmetic/Double/Proofs/Multiply | 0m16.52s || -0m01.83s | -11.13% 0m09.67s | LegacyArithmetic/Double/Proofs/RippleCarryAddSub | 0m10.78s || -0m01.10s | -10.29% 0m08.18s | Specific/X25519/C64/Synthesis | 0m09.42s || -0m01.24s | -13.16% 0m05.90s | LegacyArithmetic/InterfaceProofs | 0m07.00s || -0m01.09s | -15.71% 0m03.79s | Specific/NISTP256/FancyMachine256/Core | 0m02.62s || +0m01.16s | +44.65% 2m26.72s | Experiments/NewPipeline/Toplevel2 | 2m26.87s || -0m00.15s | -0.10% 0m43.87s | Compilers/Z/ArithmeticSimplifierWf | 0m43.11s || +0m00.75s | +1.76% 0m40.16s | Primitives/EdDSARepChange | 0m39.38s || +0m00.77s | +1.98% 0m35.17s | Specific/X25519/C32/fesub | 0m34.71s || +0m00.46s | +1.32% 0m32.73s | Arithmetic/MontgomeryReduction/WordByWord/Abstract/Dependent/Proofs | 0m31.90s || +0m00.82s | +2.60% 0m31.70s | Specific/X25519/C64/femul | 0m31.73s || -0m00.03s | -0.09% 0m26.64s | Specific/X25519/C32/Synthesis | 0m27.29s || -0m00.64s | -2.38% 0m26.24s | Compilers/Named/MapCastWf | 0m26.08s || +0m00.16s | +0.61% 0m23.26s | Specific/NISTP256/AMD128/fesub | 0m23.08s || +0m00.18s | +0.77% 0m18.97s | Specific/NISTP256/AMD128/feopp | 0m18.35s || +0m00.61s | +3.37% 0m18.31s | Compilers/Z/Syntax/Equality | 0m18.11s || +0m00.19s | +1.10% 0m18.01s | Arithmetic/MontgomeryReduction/WordByWord/Abstract/Proofs | 0m17.46s || +0m00.55s | +3.15% 0m15.18s | Arithmetic/Saturated/Core | 0m15.16s || +0m00.01s | +0.13% 0m13.76s | Arithmetic/Saturated/MontgomeryAPI | 0m13.54s || +0m00.22s | +1.62% 0m13.46s | LegacyArithmetic/Double/Proofs/ShiftRightDoubleWordImmediate | 0m13.05s || +0m00.41s | +3.14% 0m13.42s | Specific/X2448/Karatsuba/C64/Synthesis | 0m13.31s || +0m00.10s | +0.82% 0m12.81s | Arithmetic/BarrettReduction/RidiculousFish | 0m12.23s || +0m00.58s | +4.74% 0m11.69s | LegacyArithmetic/ArchitectureToZLikeProofs | 0m12.43s || -0m00.74s | -5.95% 0m10.20s | Util/FixedWordSizesEquality | 0m10.00s || +0m00.19s | +1.99% 0m10.00s | LegacyArithmetic/Pow2BaseProofs | 0m09.33s || +0m00.67s | +7.18% 0m09.96s | Util/ZUtil | 0m09.95s || +0m00.01s | +0.10% 0m09.71s | Compilers/Z/Bounds/InterpretationLemmas/PullCast | 0m09.34s || +0m00.37s | +3.96% 0m09.39s | Arithmetic/BarrettReduction/Generalized | 0m09.28s || +0m00.11s | +1.18% 0m09.28s | Specific/NISTP256/AMD64/Synthesis | 0m09.50s || -0m00.22s | -2.31% 0m08.66s | Arithmetic/Saturated/MulSplit | 0m09.52s || -0m00.85s | -9.03% 0m07.69s | Util/ZUtil/ZSimplify/Autogenerated | 0m07.29s || +0m00.40s | +5.48% 0m06.84s | Arithmetic/BarrettReduction/HAC | 0m06.50s || +0m00.33s | +5.23% 0m06.08s | LegacyArithmetic/Double/Proofs/ShiftRight | 0m06.04s || +0m00.04s | +0.66% 0m06.03s | LegacyArithmetic/ZBoundedZ | 0m06.08s || -0m00.04s | -0.82% 0m05.68s | Compilers/Z/Bounds/InterpretationLemmas/IsBoundedBy | 0m05.12s || +0m00.55s | +10.93% 0m05.65s | Compilers/Z/ArithmeticSimplifier | 0m05.02s || +0m00.63s | +12.54% 0m05.38s | Util/ZUtil/Modulo | 0m05.37s || +0m00.00s | +0.18% 0m04.96s | LegacyArithmetic/Double/Proofs/ShiftLeft | 0m04.22s || +0m00.74s | +17.53% 0m04.72s | LegacyArithmetic/Double/Proofs/Decode | 0m05.36s || -0m00.64s | -11.94% 0m04.67s | Arithmetic/ModularArithmeticTheorems | 0m05.22s || -0m00.54s | -10.53% 0m04.59s | Specific/Framework/ArithmeticSynthesis/Montgomery | 0m04.66s || -0m00.07s | -1.50% 0m04.54s | LegacyArithmetic/BarretReduction | 0m04.57s || -0m00.03s | -0.65% 0m04.52s | Compilers/Z/Bounds/Pipeline/Definition | 0m04.48s || +0m00.03s | +0.89% 0m04.30s | Util/WordUtil | 0m04.50s || -0m00.20s | -4.44% 0m03.96s | Specific/NISTP256/AMD128/Synthesis | 0m03.90s || +0m00.06s | +1.53% 0m03.87s | Arithmetic/MontgomeryReduction/WordByWord/Proofs | 0m04.60s || -0m00.72s | -15.86% 0m03.73s | Specific/NISTP256/FancyMachine256/Montgomery | 0m03.16s || +0m00.56s | +18.03% 0m03.62s | Arithmetic/Saturated/Freeze | 0m03.16s || +0m00.46s | +14.55% 0m03.60s | Compilers/Z/Bounds/Relax | 0m02.86s || +0m00.74s | +25.87% 0m03.10s | Specific/NISTP256/FancyMachine256/Barrett | 0m03.08s || +0m00.02s | +0.64% 0m03.04s | LegacyArithmetic/MontgomeryReduction | 0m02.64s || +0m00.39s | +15.15% 0m02.91s | Arithmetic/BarrettReduction/Wikipedia | 0m02.48s || +0m00.43s | +17.33% 0m02.89s | Compilers/Z/RewriteAddToAdcInterp | 0m02.17s || +0m00.72s | +33.17% 0m02.74s | Util/ZUtil/Div | 0m02.72s || +0m00.02s | +0.73% 0m02.61s | Specific/Framework/ArithmeticSynthesis/Defaults | 0m03.03s || -0m00.41s | -13.86% 0m02.52s | Specific/Framework/ReificationTypes | 0m01.76s || +0m00.76s | +43.18% 0m02.36s | Specific/Framework/ArithmeticSynthesis/Base | 0m02.42s || -0m00.06s | -2.47% 0m02.28s | Util/QUtil | 0m01.82s || +0m00.45s | +25.27% 0m02.21s | Specific/Framework/OutputType | 0m02.33s || -0m00.12s | -5.15% 0m02.15s | LegacyArithmetic/Double/Proofs/LoadImmediate | 0m02.14s || +0m00.00s | +0.46% 0m02.11s | Util/ZUtil/Quot | 0m02.08s || +0m00.02s | +1.44% 0m02.08s | LegacyArithmetic/Double/Proofs/BitwiseOr | 0m02.18s || -0m00.10s | -4.58% 0m01.92s | Experiments/NewPipeline/CLI | 0m02.03s || -0m00.10s | -5.41% 0m01.91s | Arithmetic/CoreUnfolder | 0m02.62s || -0m00.71s | -27.09% 0m01.91s | Util/ZRange/CornersMonotoneBounds | 0m01.68s || +0m00.23s | +13.69% 0m01.91s | Util/ZUtil/AddGetCarry | 0m01.88s || +0m00.03s | +1.59% 0m01.86s | LegacyArithmetic/BaseSystemProofs | 0m01.91s || -0m00.04s | -2.61% 0m01.79s | Arithmetic/PrimeFieldTheorems | 0m02.00s || -0m00.20s | -10.49% 0m01.71s | Arithmetic/Saturated/CoreUnfolder | 0m01.37s || +0m00.33s | +24.81% 0m01.66s | Experiments/NewPipeline/StandaloneOCamlMain | 0m01.62s || +0m00.03s | +2.46% 0m01.54s | Experiments/NewPipeline/StandaloneHaskellMain | 0m01.85s || -0m00.31s | -16.75% 0m01.51s | Util/NumTheoryUtil | 0m01.39s || +0m00.12s | +8.63% 0m01.44s | Compilers/Z/CommonSubexpressionElimination | 0m01.31s || +0m00.12s | +9.92% 0m01.40s | Specific/Framework/ArithmeticSynthesis/Karatsuba | 0m02.02s || -0m00.62s | -30.69% 0m01.38s | Arithmetic/Saturated/MulSplitUnfolder | 0m00.95s || +0m00.42s | +45.26% 0m01.33s | Compilers/MapCastByDeBruijnInterp | 0m01.30s || +0m00.03s | +2.30% 0m01.30s | Util/ZUtil/Stabilization | 0m01.68s || -0m00.37s | -22.61% 0m01.24s | Compilers/Z/Syntax/Util | 0m01.09s || +0m00.14s | +13.76% 0m01.22s | Arithmetic/Saturated/FreezeUnfolder | 0m01.22s || +0m00.00s | +0.00% 0m01.18s | Specific/Framework/ArithmeticSynthesis/SquareFromMul | 0m00.86s || +0m00.31s | +37.20% 0m01.14s | Arithmetic/Saturated/WrappersUnfolder | 0m01.53s || -0m00.39s | -25.49% 0m01.13s | Arithmetic/Saturated/Wrappers | 0m01.10s || +0m00.02s | +2.72% 0m01.12s | Specific/Framework/ArithmeticSynthesis/FreezePackage | 0m01.10s || +0m00.02s | +1.81% 0m01.12s | Specific/Framework/ArithmeticSynthesis/LadderstepPackage | 0m00.98s || +0m00.14s | +14.28% 0m01.10s | Specific/Framework/ArithmeticSynthesis/BasePackage | 0m01.11s || -0m00.01s | -0.90% 0m01.09s | Arithmetic/Saturated/UniformWeight | 0m00.92s || +0m00.17s | +18.47% 0m01.08s | LegacyArithmetic/Double/Proofs/SelectConditional | 0m01.05s || +0m00.03s | +2.85% 0m01.05s | Specific/Framework/SynthesisFramework | 0m01.03s || +0m00.02s | +1.94% 0m01.03s | Specific/Framework/ReificationTypesPackage | 0m01.16s || -0m00.12s | -11.20% 0m01.01s | Specific/Framework/MontgomeryReificationTypes | 0m01.03s || -0m00.02s | -1.94% 0m00.99s | LegacyArithmetic/Double/Core | 0m00.98s || +0m00.01s | +1.02% 0m00.98s | Arithmetic/MontgomeryReduction/WordByWord/Definition | 0m00.81s || +0m00.16s | +20.98% 0m00.95s | Compilers/MapCastByDeBruijnWf | 0m00.71s || +0m00.24s | +33.80% 0m00.95s | Specific/Framework/ArithmeticSynthesis/Freeze | 0m01.25s || -0m00.30s | -24.00% 0m00.94s | Specific/Framework/ArithmeticSynthesis/DefaultsPackage | 0m01.11s || -0m00.17s | -15.31% 0m00.93s | LegacyArithmetic/Interface | 0m01.02s || -0m00.08s | -8.82% 0m00.91s | Arithmetic/ModularArithmeticPre | 0m00.87s || +0m00.04s | +4.59% 0m00.90s | Compilers/Z/Bounds/Pipeline/ReflectiveTactics | 0m00.92s || -0m00.02s | -2.17% 0m00.90s | Compilers/Z/Reify | 0m00.89s || +0m00.01s | +1.12% 0m00.90s | Specific/Framework/ArithmeticSynthesis/HelperTactics | 0m01.09s || -0m00.19s | -17.43% 0m00.89s | Compilers/Z/Bounds/MapCastByDeBruijnInterp | 0m00.94s || -0m00.04s | -5.31% 0m00.88s | Compilers/Z/Bounds/Pipeline/Glue | 0m00.91s || -0m00.03s | -3.29% 0m00.88s | LegacyArithmetic/ArchitectureToZLike | 0m00.80s || +0m00.07s | +9.99% 0m00.88s | Specific/Framework/ArithmeticSynthesis/Ladderstep | 0m01.09s || -0m00.21s | -19.26% 0m00.86s | Compilers/Z/Bounds/MapCastByDeBruijnWf | 0m00.69s || +0m00.17s | +24.63% 0m00.84s | Compilers/Z/Bounds/InterpretationLemmas/Tactics | 0m00.84s || +0m00.00s | +0.00% 0m00.83s | Arithmetic/Saturated/UniformWeightInstances | 0m00.73s || +0m00.09s | +13.69% 0m00.82s | Compilers/Z/InlineConstAndOpByRewriteWf | 0m00.76s || +0m00.05s | +7.89% 0m00.81s | Compilers/Z/ArithmeticSimplifierUtil | 0m00.84s || -0m00.02s | -3.57% 0m00.81s | Compilers/Z/CommonSubexpressionEliminationInterp | 0m00.86s || -0m00.04s | -5.81% 0m00.81s | Compilers/Z/MapCastByDeBruijnInterp | 0m00.87s || -0m00.05s | -6.89% 0m00.81s | Util/ZUtil/Tactics/RewriteModSmall | 0m00.79s || +0m00.02s | +2.53% 0m00.80s | Compilers/Z/MapCastByDeBruijnWf | 0m00.78s || +0m00.02s | +2.56% 0m00.80s | LegacyArithmetic/Double/Proofs/ShiftLeftRightTactic | 0m00.76s || +0m00.04s | +5.26% 0m00.80s | LegacyArithmetic/ZBounded | 0m00.88s || -0m00.07s | -9.09% 0m00.79s | Compilers/Z/CommonSubexpressionEliminationWf | 0m00.88s || -0m00.08s | -10.22% 0m00.79s | LegacyArithmetic/Pow2Base | 0m00.76s || +0m00.03s | +3.94% 0m00.78s | Compilers/Z/Bounds/MapCastByDeBruijn | 0m00.82s || -0m00.03s | -4.87% 0m00.78s | Compilers/Z/InlineConstAndOpWf | 0m00.80s || -0m00.02s | -2.50% 0m00.78s | Compilers/Z/InlineWf | 0m00.64s || +0m00.14s | +21.87% 0m00.78s | Spec/EdDSA | 0m00.74s || +0m00.04s | +5.40% 0m00.78s | Specific/Framework/ArithmeticSynthesis/MontgomeryPackage | 0m00.73s || +0m00.05s | +6.84% 0m00.77s | Compilers/Z/InlineConstAndOpByRewriteInterp | 0m00.78s || -0m00.01s | -1.28% 0m00.76s | Arithmetic/MontgomeryReduction/Definition | 0m00.76s || +0m00.00s | +0.00% 0m00.76s | Compilers/Z/InlineConstAndOp | 0m00.74s || +0m00.02s | +2.70% 0m00.74s | Specific/Framework/MontgomeryReificationTypesPackage | 0m00.76s || -0m00.02s | -2.63% 0m00.74s | Util/ZUtil/CC | 0m00.76s || -0m00.02s | -2.63% 0m00.74s | Util/ZUtil/EquivModulo | 0m00.76s || -0m00.02s | -2.63% 0m00.73s | Compilers/Z/InlineInterp | 0m00.61s || +0m00.12s | +19.67% 0m00.72s | Compilers/Z/InlineConstAndOpInterp | 0m00.74s || -0m00.02s | -2.70% 0m00.72s | LegacyArithmetic/BaseSystem | 0m00.82s || -0m00.09s | -12.19% 0m00.71s | Compilers/Z/InlineConstAndOpByRewrite | 0m00.70s || +0m00.01s | +1.42% 0m00.71s | Compilers/Z/InterpSideConditions | 0m00.74s || -0m00.03s | -4.05% 0m00.67s | Compilers/Z/FoldTypes | 0m00.70s || -0m00.02s | -4.28% 0m00.67s | Specific/Framework/ArithmeticSynthesis/KaratsubaPackage | 0m01.09s || -0m00.42s | -38.53% 0m00.65s | Compilers/Z/Bounds/Pipeline | 0m00.72s || -0m00.06s | -9.72% 0m00.65s | Compilers/Z/Inline | 0m00.72s || -0m00.06s | -9.72% 0m00.65s | Compilers/ZExtended/MapBaseType | 0m00.74s || -0m00.08s | -12.16% 0m00.63s | Util/NUtil | 0m00.98s || -0m00.35s | -35.71% 0m00.48s | Spec/ModularArithmetic | 0m00.72s || -0m00.24s | -33.33% 0m00.36s | Util/ZUtil/Div/Bootstrap | N/A || +0m00.36s | ∞ 0m00.36s | Util/ZUtil/Modulo/Bootstrap | N/A || +0m00.36s | ∞ 0m00.36s | Util/ZUtil/Tactics | 0m00.38s || -0m00.02s | -5.26% 0m00.36s | Util/ZUtil/Tactics/SimplifyFractionsLe | 0m00.36s || +0m00.00s | +0.00% 0m00.34s | Util/ZUtil/Tactics/ZeroBounds | 0m00.33s || +0m00.01s | +3.03% 0m00.32s | Util/ZUtil/Tactics/DivModToQuotRem | 0m00.27s || +0m00.04s | +18.51% 0m00.32s | Util/ZUtil/ZSimplify | 0m00.29s || +0m00.03s | +10.34%
* Make all parameters implicitGravatar Jasper Hugunin2018-07-02
|
* remove commentGravatar Jade Philipoom2018-04-11
|
* add a comment to rerun buildGravatar Jade Philipoom2018-04-11
|
* Automate some proofs a bit moreGravatar Jason Gross2018-04-11
|
* try to fix build on coq masterGravatar Jade Philipoom2018-04-11
|
* prove stronger bound on quotient error for barrett reductionGravatar Jade Philipoom2018-04-11
|
* Review comments.Gravatar David Benjamin2018-03-09
| | | | | | | Major change is porting everything to Z and using Z.div_mod_to_quot_rem which is a handy sledgehammer. Z is also a nice simplification. Dealing with subtraction is tidier, though I do have 0 <= x goals everywhere as a result.
* easy bitsGravatar David Benjamin2018-03-09
|
* Prove another Barrett reduction variant.Gravatar David Benjamin2018-03-09
| | | | | | | | | | This variant comes from http://www.ridiculousfish.com/blog/posts/labor-of-division-episode-i.html. It was useful for https://boringssl-review.googlesource.com/#/c/boringssl/+/25887. TODO - Talk to Andres to figure out all the ways this could be done more cleanly. It was originally a standalone file.
* Fix naming issueGravatar Jade Philipoom2018-02-23
|
* add equivalence proof for Montgomery reduce_via_partial_altGravatar Jade Philipoom2018-02-23
|
* Add MontgomeryAPI.encode and two lemmas about itGravatar Jason Gross2017-11-14
| | | | One of them is Admitted.
* fix commentGravatar jadep2017-11-12
|
* Fix another side condition issueGravatar Jason Gross2017-11-08
|
* Fix a bug in previous commitGravatar Jason Gross2017-11-08
|
* Add freeze rewrite lemmas to dbsGravatar Jason Gross2017-11-08
|
* Add karatsuba, goldilocks lemmas to rewrite dbsGravatar Jason Gross2017-11-07
|
* Move chained_carries' (now chained_carries_reduce)Gravatar Jason Gross2017-11-07
| | | | | | | | | | It now lives in Arithmetic.Core.B.Positional, where it belongs, rather than in Specific/.../HelperTactics. Andres notes that we probably don't need this at all, and could instead make chained_carries reduce after every index (and the spurious reductions should be no-ops). I didn't want to bother verifying this, at the moment, so I left it as-is.
* Add more versions of basesystem_partial_evaluation_unfolderGravatar Jason Gross2017-11-07
|
* Split off computational part of basesystem_partial_evaluation_RHS_genGravatar Jason Gross2017-11-07
|
* More use of Z.eqb_cpsGravatar Jason Gross2017-11-07
|
* Use div_cps and modulo_cps in more placesGravatar Jason Gross2017-11-07
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | After | File Name | Before || Change | % Change -------------------------------------------------------------------------------------------------------- 10m04.41s | Total | 10m03.68s || +0m00.73s | +0.12% -------------------------------------------------------------------------------------------------------- 3m04.06s | Specific/X25519/C64/ladderstep | 3m04.00s || +0m00.06s | +0.03% 1m48.23s | Specific/NISTP256/AMD64/femul | 1m48.30s || -0m00.07s | -0.06% 0m38.59s | Arithmetic/Karatsuba | 0m38.51s || +0m00.08s | +0.20% 0m22.50s | Specific/X25519/C64/femul | 0m23.15s || -0m00.64s | -2.80% 0m21.79s | Specific/NISTP256/AMD64/fesub | 0m21.76s || +0m00.02s | +0.13% 0m19.78s | Specific/NISTP256/AMD64/feadd | 0m19.94s || -0m00.16s | -0.80% 0m18.57s | Specific/X25519/C64/freeze | 0m18.57s || +0m00.00s | +0.00% 0m17.96s | Specific/X25519/C64/fesquare | 0m18.36s || -0m00.39s | -2.17% 0m16.54s | Specific/NISTP256/AMD64/feopp | 0m16.18s || +0m00.35s | +2.22% 0m14.58s | Specific/X25519/C64/fecarry | 0m14.76s || -0m00.17s | -1.21% 0m13.80s | Specific/NISTP256/AMD64/fenz | 0m13.84s || -0m00.03s | -0.28% 0m13.34s | Specific/X25519/C64/fesub | 0m13.57s || -0m00.23s | -1.69% 0m12.72s | Arithmetic/Saturated/AddSub | 0m12.74s || -0m00.01s | -0.15% 0m12.19s | Specific/X25519/C64/feadd | 0m12.48s || -0m00.29s | -2.32% 0m10.57s | Arithmetic/Saturated/MontgomeryAPI | 0m10.36s || +0m00.21s | +2.02% 0m10.17s | Arithmetic/Saturated/Core | 0m09.92s || +0m00.25s | +2.52% 0m06.47s | Specific/NISTP256/AMD64/Synthesis | 0m06.65s || -0m00.18s | -2.70% 0m06.02s | Arithmetic/Saturated/MulSplit | 0m05.87s || +0m00.14s | +2.55% 0m05.27s | Specific/X25519/C64/Synthesis | 0m05.45s || -0m00.18s | -3.30% 0m03.70s | Arithmetic/MontgomeryReduction/WordByWord/Proofs | 0m03.65s || +0m00.05s | +1.36% 0m03.66s | Specific/Framework/ArithmeticSynthesis/Montgomery | 0m03.70s || -0m00.04s | -1.08% 0m02.93s | Specific/Framework/ArithmeticSynthesis/Defaults | 0m02.60s || +0m00.33s | +12.69% 0m02.42s | Arithmetic/Saturated/Freeze | 0m02.45s || -0m00.03s | -1.22% 0m01.57s | Arithmetic/CoreUnfolder | 0m01.52s || +0m00.05s | +3.28% 0m01.44s | Specific/Framework/ArithmeticSynthesis/HelperTactics | 0m01.11s || +0m00.32s | +29.72% 0m01.29s | Specific/Framework/ArithmeticSynthesis/Karatsuba | 0m01.21s || +0m00.08s | +6.61% 0m01.19s | Specific/Framework/ArithmeticSynthesis/Base | 0m01.00s || +0m00.18s | +18.99% 0m01.04s | Arithmetic/Saturated/CoreUnfolder | 0m01.13s || -0m00.08s | -7.96% 0m01.00s | Arithmetic/Saturated/UniformWeight | 0m00.95s || +0m00.05s | +5.26% 0m00.92s | Arithmetic/Saturated/WrappersUnfolder | 0m00.96s || -0m00.03s | -4.16% 0m00.89s | Specific/Framework/SynthesisFramework | 0m01.00s || -0m00.10s | -10.99% 0m00.87s | Specific/Framework/ReificationTypes | 0m01.00s || -0m00.13s | -13.00% 0m00.84s | Specific/Framework/MontgomeryReificationTypesPackage | 0m00.82s || +0m00.02s | +2.43% 0m00.81s | Specific/Framework/ArithmeticSynthesis/MontgomeryPackage | 0m00.72s || +0m00.09s | +12.50% 0m00.80s | Specific/Framework/ArithmeticSynthesis/Freeze | 0m00.86s || -0m00.05s | -6.97% 0m00.78s | Arithmetic/MontgomeryReduction/WordByWord/Definition | 0m00.76s || +0m00.02s | +2.63% 0m00.77s | Specific/Framework/MontgomeryReificationTypes | 0m00.80s || -0m00.03s | -3.75% 0m00.76s | Arithmetic/Saturated/MulSplitUnfolder | 0m00.80s || -0m00.04s | -5.00% 0m00.76s | Specific/Framework/ArithmeticSynthesis/DefaultsPackage | 0m00.70s || +0m00.06s | +8.57% 0m00.75s | Specific/Framework/ArithmeticSynthesis/KaratsubaPackage | 0m00.64s || +0m00.10s | +17.18% 0m00.75s | Specific/Framework/ArithmeticSynthesis/LadderstepPackage | 0m00.71s || +0m00.04s | +5.63% 0m00.74s | Arithmetic/Saturated/Wrappers | 0m00.78s || -0m00.04s | -5.12% 0m00.73s | Arithmetic/Saturated/FreezeUnfolder | 0m00.77s || -0m00.04s | -5.19% 0m00.72s | Specific/Framework/ArithmeticSynthesis/SquareFromMul | 0m00.72s || +0m00.00s | +0.00% 0m00.72s | Specific/Framework/ReificationTypesPackage | 0m00.84s || -0m00.12s | -14.28% 0m00.71s | Specific/Framework/ArithmeticSynthesis/FreezePackage | 0m00.69s || +0m00.02s | +2.89% 0m00.70s | Specific/Framework/ArithmeticSynthesis/Ladderstep | 0m00.67s || +0m00.02s | +4.47% 0m00.69s | Specific/Framework/ArithmeticSynthesis/BasePackage | 0m01.03s || -0m00.34s | -33.00% 0m00.66s | Arithmetic/Saturated/UniformWeightInstances | 0m00.67s || -0m00.01s | -1.49% 0m15.65s | Arithmetic/Core | 0m14.01s || +0m01.64s | +11.70%
* Make use of id_tuple_with_alt_cps'Gravatar Jason Gross2017-11-06
|
* Make use of from_associational_cps in more placesGravatar Jason Gross2017-11-01
|
* More use of Z.eqb_cpsGravatar Jason Gross2017-11-01
|
* Add another unfolding databaseGravatar Jason Gross2017-10-22
|
* Fix bug in previous commitGravatar Jason Gross2017-10-20
|
* Use div_cps, modulo_cpsGravatar Jason Gross2017-10-20
|
* Use fold_right_cps2 to get eqb_cps to get the right continuation typeGravatar Jason Gross2017-10-19
|
* Add more unfolds to basesystem_partial_evaluation_unfolderGravatar Jason Gross2017-10-19
|
* Switch arithmetic to cps for Z * Z under the hoodGravatar Jason Gross2017-10-19
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is in preparation for writing a ~compiler for the arithmetic things to expression trees. I'm not sure what's up with femul in the table below; I ran it again and got: After: src/Specific/NISTP256/AMD64/femul (real: 115.70, user: 115.25, sys: 0.44, mem: 3571448 ko) Before: src/Specific/NISTP256/AMD64/femul (real: 118.49, user: 117.99, sys: 0.43, mem: 3581612 ko) After | File Name | Before || Change --------------------------------------------------------------------------------------------- 17m02.82s | Total | 16m36.20s || +0m26.61s --------------------------------------------------------------------------------------------- 2m27.04s | Specific/NISTP256/AMD64/femul | 2m04.60s || +0m22.43s 1m38.55s | Specific/X2448/Karatsuba/C64/femul | 1m41.44s || -0m02.89s 0m12.46s | Arithmetic/Saturated/AddSub | 0m09.77s || +0m02.69s 3m22.38s | Specific/X25519/C64/ladderstep | 3m23.49s || -0m01.11s 0m54.40s | Specific/X25519/C32/fesquare | 0m52.68s || +0m01.71s 0m28.70s | Arithmetic/Karatsuba | 0m27.59s || +0m01.10s 0m10.00s | Arithmetic/Saturated/MontgomeryAPI | 0m08.95s || +0m01.05s 0m08.15s | Specific/X2448/Karatsuba/C64/Synthesis | 0m09.47s || -0m01.32s 0m05.62s | Arithmetic/Saturated/MulSplit | 0m04.28s || +0m01.33s 1m29.44s | Specific/X25519/C32/femul | 1m28.55s || +0m00.89s 0m39.38s | Specific/X25519/C32/freeze | 0m38.62s || +0m00.76s 0m31.54s | Specific/NISTP256/AMD128/femul | 0m31.60s || -0m00.06s 0m24.80s | Specific/X25519/C64/femul | 0m24.10s || +0m00.69s 0m23.82s | Specific/NISTP256/AMD64/fesub | 0m23.52s || +0m00.30s 0m21.81s | Specific/NISTP256/AMD64/feadd | 0m21.90s || -0m00.08s 0m20.30s | Specific/X25519/C64/freeze | 0m20.26s || +0m00.03s 0m20.12s | Specific/X25519/C32/Synthesis | 0m20.77s || -0m00.64s 0m19.12s | Specific/X25519/C64/fesquare | 0m19.02s || +0m00.10s 0m17.28s | Specific/NISTP256/AMD64/feopp | 0m17.68s || -0m00.39s 0m15.99s | Specific/NISTP256/AMD128/fesub | 0m16.03s || -0m00.04s 0m15.88s | Specific/NISTP256/AMD128/feadd | 0m16.56s || -0m00.67s 0m15.03s | Specific/NISTP256/AMD64/fenz | 0m15.00s || +0m00.02s 0m14.18s | Specific/NISTP256/AMD128/fenz | 0m14.12s || +0m00.06s 0m13.46s | Specific/NISTP256/AMD128/feopp | 0m12.88s || +0m00.58s 0m12.15s | Arithmetic/Core | 0m12.03s || +0m00.12s 0m07.82s | Arithmetic/Saturated/Core | 0m07.05s || +0m00.77s 0m07.13s | Specific/NISTP256/AMD64/Synthesis | 0m08.05s || -0m00.92s 0m05.48s | Specific/X25519/C64/Synthesis | 0m05.68s || -0m00.19s 0m04.02s | Specific/Framework/ArithmeticSynthesis/Montgomery | 0m03.89s || +0m00.12s 0m03.52s | Arithmetic/MontgomeryReduction/WordByWord/Proofs | 0m03.34s || +0m00.18s 0m03.32s | Specific/NISTP256/AMD128/Synthesis | 0m03.46s || -0m00.14s 0m02.30s | Specific/Framework/ArithmeticSynthesis/Defaults | 0m02.31s || -0m00.01s 0m02.08s | Arithmetic/Saturated/Freeze | 0m01.94s || +0m00.14s 0m01.66s | Specific/Framework/OutputType | 0m01.66s || +0m00.00s 0m01.54s | Arithmetic/CoreUnfolder | 0m01.43s || +0m00.11s 0m01.35s | Specific/Framework/ArithmeticSynthesis/Karatsuba | 0m01.28s || +0m00.07s 0m01.13s | Arithmetic/Saturated/CoreUnfolder | 0m01.16s || -0m00.03s 0m01.06s | Arithmetic/Saturated/WrappersUnfolder | 0m01.04s || +0m00.02s 0m01.04s | Arithmetic/Saturated/UniformWeight | 0m00.95s || +0m00.09s 0m01.03s | Specific/Framework/ArithmeticSynthesis/Base | 0m01.14s || -0m00.10s 0m01.02s | Specific/Framework/SynthesisFramework | 0m01.04s || -0m00.02s 0m00.97s | Specific/Framework/ArithmeticSynthesis/HelperTactics | 0m01.01s || -0m00.04s 0m00.92s | Specific/Framework/ReificationTypes | 0m00.90s || +0m00.02s 0m00.92s | Specific/Framework/ArithmeticSynthesis/Freeze | 0m00.93s || -0m00.01s 0m00.90s | Arithmetic/Saturated/MulSplitUnfolder | 0m00.83s || +0m00.07s 0m00.83s | Specific/Framework/ReificationTypesPackage | 0m00.79s || +0m00.03s 0m00.83s | Arithmetic/Saturated/FreezeUnfolder | 0m00.86s || -0m00.03s 0m00.82s | Specific/Framework/ArithmeticSynthesis/BasePackage | 0m00.77s || +0m00.04s 0m00.81s | Specific/Framework/ArithmeticSynthesis/SquareFromMul | 0m00.72s || +0m00.09s 0m00.81s | Specific/Framework/ArithmeticSynthesis/LadderstepPackage | 0m00.82s || -0m00.00s 0m00.80s | Specific/Framework/MontgomeryReificationTypesPackage | 0m00.82s || -0m00.01s 0m00.78s | Specific/Framework/ArithmeticSynthesis/MontgomeryPackage | 0m00.79s || -0m00.01s 0m00.78s | Arithmetic/Saturated/Wrappers | 0m00.78s || +0m00.00s 0m00.76s | Specific/Framework/ArithmeticSynthesis/FreezePackage | 0m00.80s || -0m00.04s 0m00.76s | Specific/Framework/ArithmeticSynthesis/DefaultsPackage | 0m00.75s || +0m00.01s 0m00.75s | Specific/Framework/MontgomeryReificationTypes | 0m00.78s || -0m00.03s 0m00.73s | Specific/Framework/ArithmeticSynthesis/Ladderstep | 0m00.77s || -0m00.04s 0m00.73s | Arithmetic/MontgomeryReduction/WordByWord/Definition | 0m00.80s || -0m00.07s 0m00.72s | Arithmetic/Saturated/UniformWeightInstances | 0m00.78s || -0m00.06s 0m00.68s | Specific/Framework/ArithmeticSynthesis/KaratsubaPackage | 0m00.76s || -0m00.07s 0m00.43s | Util/ZUtil/CPS | 0m00.42s || +0m00.01s
* Move tactics around in src/Arithmetic/CoreUnfolder.vGravatar Jason Gross2017-10-19
| | | | Also unfold some cps things
* Pattern over cps lemmas in Arithmetic/CoreGravatar Jason Gross2017-10-19
|
* Unfold more things in basesystem_partial_evaluation_unfolderGravatar Jason Gross2017-10-18
|
* Add some more things to basesystem_partial_evaluation_unfolderGravatar Jason Gross2017-10-18
|
* Add basesystem_partial_evaluation_unfolder dbGravatar Jason Gross2017-10-18
|
* Unfold more things in core unfolderGravatar Jason Gross2017-10-18
|
* Allow instantiating type arguments without reducing matchesGravatar Jason Gross2017-10-18
|
* Pattern more things in arithmetic/coreGravatar Jason Gross2017-10-17
|
* Add MulSplitUnfolderGravatar Jason Gross2017-10-17
|
* Add faster arithmetic unfoldingGravatar Jason Gross2017-10-15
|
* Extend basesystem_partial_evaluation_RHSGravatar Jason Gross2017-10-15
| | | | | Now there's a version that handles things in Saturated.Core, and in Wrappers.
* Fix a typo in the previous commitGravatar Jason Gross2017-10-14
|
* Split up solve_op_mod_eqGravatar Jason Gross2017-10-14
| | | | This way, we can reuse it even when we can't fully compute the values
* Add UniformWeightInstancesGravatar Jason Gross2017-10-09
|
* Add cbv_runtime in Arithmetic/CoreGravatar Jason Gross2017-07-08
| | | | This way, files importing Core don't have to keep track of the list of runtime operations, for unfoling.
* More fine-grained tactics importsGravatar Jason Gross2017-07-08
|
* Remove some admitted lemmasGravatar Jason Gross2017-07-07
|
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-27 03:16:18 +0000