Last active
December 18, 2021 16:32
-
-
Save halcwb/273dd2af3c241bbe2908d4099a361ae8 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#r "nuget: MathNet.Numerics.FSharp" | |
#r "nuget: Expecto" | |
#r "nuget: Expecto.FsCheck" | |
#time | |
module BigInteger = | |
open System | |
open MathNet.Numerics | |
let fromInt (x : int) = bigint(x) | |
let toInt (x : bigint) = int x | |
module Set = | |
open System | |
open MathNet.Numerics | |
let calc op (s1 : Set<_>) (s2 : Set<_>) = | |
Seq.allPairs s1 s2 | |
|> Seq.map (fun (x1, x2) -> x1 |> op <| x2) | |
|> Set.ofSeq | |
let gcd (xs : bigint seq) = | |
Euclid.GreatestCommonDivisor(xs |> Array.ofSeq) | |
let lcm (xs : bigint seq) = | |
Euclid.LeastCommonMultiple(xs |> Array.ofSeq) | |
module Types = | |
open System | |
open MathNet.Numerics | |
/// The minimal value in | |
/// a `Range`. Can be inclusive | |
/// or exclusive. | |
type Minimum = | |
| MinIncl of BigRational | |
| MinExcl of BigRational | |
/// The maximum value in | |
/// a `Range`. Can be inclusive | |
/// or exclusive. | |
type Maximum = | |
| MaxIncl of BigRational | |
| MaxExcl of BigRational | |
type Range = | |
{ | |
Minimum : Minimum option | |
Multiples : bigint Set | |
Delta : BigRational option | |
Maximum : Maximum option | |
} | |
type Operators = | |
| Mult | |
| Div | |
| Add | |
| Subtr | |
module Operator = | |
open Types | |
let inline getOp op = | |
match op with | |
| Mult -> (*) | |
| Div -> (/) | |
| Add -> (+) | |
| Subtr -> (-) | |
module Range = | |
open System | |
open MathNet.Numerics | |
open Types | |
let isBetween min max x = | |
match min, max with | |
| Some (MinIncl min), Some (MaxIncl max) -> min >= x && x <= max | |
| Some (MinIncl min), Some (MaxExcl max) -> min >= x && x < max | |
| Some (MinExcl min), Some (MaxIncl max) -> min > x && x <= max | |
| Some (MinExcl min), Some (MaxExcl max) -> min > x && x < max | |
| Some (MinIncl min), None -> min >= x | |
| Some (MinExcl min), None -> min > x | |
| None, Some (MaxExcl max) -> x < max | |
| None, Some (MaxIncl max) -> x <= max | |
| None, None -> true | |
let create min max delta mults = | |
{ | |
Minimum = min | |
Multiples = | |
match delta with | |
| Some d -> | |
mults | |
|> Seq.filter (fun x -> | |
x | |
|> BigRational.FromBigInt | |
|> ((*) d) | |
|> isBetween min max | |
) | |
|> Set.ofSeq | |
| None -> Set.empty | |
Delta = delta | |
Maximum = max | |
} | |
let createFromIntMultiples delta mults = | |
mults | |
|> Seq.map BigInteger.fromInt | |
|> Set.ofSeq | |
|> create None None (Some delta) | |
let unrestricted = create None None None Set.empty | |
let toSet (r : Range) = | |
match r.Delta with | |
| None -> Set.empty | |
| Some d -> | |
r.Multiples | |
|> Set.map BigRational.FromBigInt | |
|> Set.map ((*) d) | |
let scale up range n = | |
match range.Delta with | |
| None -> range | |
| Some d -> | |
{ | |
range with | |
Multiples = | |
range.Multiples | |
|> Set.map (fun x -> | |
if up then x * n else x / n | |
) | |
Delta = | |
let n = n |> BigRational.FromBigInt | |
if up then d / n else d * n | |
|> Some | |
} | |
let scaleUp = scale true | |
let scaleDown = scale false | |
/// filters out all r2 multiples that | |
/// cannot divide any of the r1 multiples | |
let nonDivisible r1 r2 = | |
r2.Multiples | |
|> Set.filter (fun m2 -> | |
r1.Multiples | |
|> Set.exists (fun m1 -> m1 % m2 = 0I) | |
|> not | |
) | |
let intersectWith r2 r1 = | |
{ | |
r2 with | |
Multiples = | |
if r2.Multiples |> Set.isEmpty then r1.Multiples | |
else | |
r1.Multiples | |
|> Set.intersect r2.Multiples | |
Delta = | |
if r2.Delta |> Option.isNone then r1.Delta | |
else | |
r2.Delta | |
// should check the same as r1 | |
} | |
let calc op (r3 : Range) (r1 : Range) (r2 : Range) = | |
// scale r1 if division to make it | |
// divisible by r2 | |
let r1 = | |
if op <> Div then r1 | |
else | |
nonDivisible r1 r2 | |
|> Set.lcm | |
|> scaleUp r1 | |
match r1.Delta, r2.Delta with | |
| Some d1, Some d2 -> | |
let delta = | |
match op with | |
| Add | Subtr _ when d1 = d2 -> d2 | |
| Mult | Div -> | |
d1 |> (op |> Operator.getOp) <| d2 | |
| _ -> | |
failwith (sprintf "cannot process") | |
let between x = | |
match r3.Delta with | |
| None -> true | |
| Some d -> | |
x | |
|> BigRational.FromBigInt | |
|> ((*) d) | |
|> isBetween r3.Minimum r3.Maximum | |
{ | |
Minimum = r3.Minimum | |
Multiples = | |
set [ | |
for x1 in r1.Multiples do | |
for x2 in r2.Multiples do | |
match op with | |
| Mult -> x1 * x2 | |
| Div -> if x1 % x2 = 0I then x1 / x2 | |
| Add -> x1 + x2 | |
| Subtr -> if x1 - x2 > 0I then x1 - x2 | |
] | |
|> Set.filter between | |
Delta = Some delta | |
Maximum = r3.Maximum | |
} | |
|> intersectWith r3 | |
| _ -> | |
// Need to do min max calculations | |
failwith "not implemented yet" | |
let multiply = calc Mult | |
let divide = calc Div | |
let add = calc Add | |
let subtr = calc Subtr | |
open System | |
open MathNet.Numerics | |
open Types | |
let testRange op r1Multiples r1Delta r2Multiples r2Delta = | |
let r1 = r1Multiples |> List.map BigInteger.fromInt |> Range.create None None (Some r1Delta) | |
let r2 = r2Multiples |> List.map BigInteger.fromInt |> Range.create None None (Some r2Delta) | |
// r3 = r1 op r2 | |
let r3 = Range.calc op Range.unrestricted r1 r2 | |
let s1 = r1 |> Range.toSet | |
let s2 = r2 |> Range.toSet | |
let s3 = | |
let s3 = Set.calc (op |> Operator.getOp) s1 s2 | |
match op with | |
| Div -> | |
// assume div is also discreet | |
let d = r1Delta / r2Delta | |
s3 | |
|> Set.filter (fun x -> | |
(x / d).Denominator = 1I | |
) | |
| Subtr -> | |
s3 | |
// negative values not allowed | |
|> Set.filter (fun x -> x > 0N) | |
| _ -> s3 | |
if r3 |> Range.toSet = s3 then printfn "pass set test" | |
else | |
printfn "failed set test" | |
printfn "== Actual" | |
r3 | |
|> Range.toSet | |
|> Seq.iteri (fun i x -> | |
printfn $"{i}. {x}" | |
) | |
printfn "== Expected" | |
s3 | |
|> Seq.iteri (fun i x -> | |
printfn $"{i}. {x}" | |
) | |
let test s act exp = | |
printfn "test: %s" s | |
if act.Delta= exp.Delta then printfn "pass delta test" | |
else | |
printfn "failed delta test" | |
printfn "== Actual" | |
printfn $"{act.Delta}" | |
printfn "== Expected" | |
printfn $"{exp.Delta}" | |
if exp.Multiples | |
|> Seq.forall (fun x -> act.Multiples |> Seq.exists ((=) x)) then | |
printfn "pass multiples test" | |
else | |
printfn "failed multiples test" | |
printfn "== Actual" | |
act.Multiples | |
|> Seq.iteri (fun i x -> | |
printfn $"{i}. {x}" | |
) | |
printfn "== Expected" | |
exp.Multiples | |
|> Seq.iteri (fun i x -> | |
printfn $"{i}. {x}" | |
) | |
match op with | |
| Mult -> | |
// r3 = r1 * r2 | |
// r1 = r3 / r2 | |
test "r1 = r3 / r2" (Range.calc Div r1 r3 r2) r1 | |
// r2 = r3 / r1 | |
test "r2 = r3 / r1" (Range.calc Div r2 r3 r1) r2 | |
| Div -> | |
// r3 = r1 / r2 | |
// r1 = r3 * r2 | |
test "r1 = r3 * r2" (Range.calc Mult r1 r3 r2) r1 | |
// r2 = r1 / r3 | |
test "r2 = r1 / r3" (Range.calc Div r2 r1 r3) r2 | |
| Add -> | |
// r3 = r1 + r2 | |
// r1 = r3 - r2 | |
test "r1 = r3 - r2" (Range.calc Subtr r1 r3 r2) r1 | |
// r2 = r3 - r1 | |
test "r2 = r3 - r1" (Range.calc Subtr r2 r3 r1) r2 | |
| Subtr -> | |
// r3 = r1 - r2 | |
// r1 = r3 + r2 | |
test "r1 = r3 + r2" (Range.calc Add r1 r3 r2) r1 | |
// r2 = r1 - r3 | |
test "r2 = r1 - r3" (Range.calc Subtr r2 r1 r3) r2 | |
testRange Mult [1;2;3] 2N [1;2;3] 3N | |
testRange Mult [2;3;4] 2N [1;2;3] 3N | |
testRange Mult [2;3;4] 2N [2;3;4] 3N | |
testRange Mult [2;3;4] 2N [12;13;14] 3N | |
testRange Mult [1..99] 2N [1..100] 3N | |
testRange Mult [1;2;3] (1N/2N) [1;2;3] (1N/3N) | |
testRange Mult [2;7;15] 2N [3;8;12] 3N | |
testRange Div [1;2;3] 4N [1;2;3] 2N | |
testRange Div [2;3;4] 2N [1;2;3] 3N | |
testRange Div [2;3;4] 2N [2;3;4] 3N | |
// fails | |
testRange Div [2;3;4] 2N [12;13;14] 3N | |
testRange Div [1..100] 2N [1..99] 3N | |
testRange Div [1;2;3] (1N/2N) [1;2;3] (1N/3N) | |
// fails | |
testRange Div [6;7;15] 2N [3;8;12] 3N | |
testRange Add [1;2;3] 4N [1;2;3] 4N | |
testRange Add [2;3;4] 2N [1;2;3] 2N | |
testRange Add [2;3;4] 2N [2;3;4] 2N | |
testRange Add [2;3;4] 2N [12;13;14] 2N | |
testRange Add [1..100] 2N [1..99] 2N | |
testRange Add [1;2;3] (1N/2N) [1;2;3] (1N/2N) | |
testRange Add [2;7;15] 2N [3;8;12] 2N | |
testRange Subtr [2;3;4] 4N [1;2;3] 4N | |
testRange Subtr [2;3;4] 2N [1;2;3] 2N | |
testRange Subtr [3;4;5] 2N [2;3;4] 2N | |
testRange Subtr [12;13;14] 2N [2;3;4] 2N | |
testRange Subtr [2..100] 2N [1..99] 2N | |
testRange Subtr [2;3;4] (1N/2N) [1;2;3] (1N/2N) | |
// fails | |
testRange Subtr [2;7;15] 2N [13;18;112] 2N | |
// fix for failing tests | |
let r1 = Range.createFromIntMultiples 2N [2;3;4] | |
let r2 = Range.createFromIntMultiples 3N [12;13;14] | |
let r1' = | |
Range.nonDivisible r1 r2 | |
|> Set.lcm | |
|> Range.scaleUp r1 | |
r1 |> Range.toSet = (r1' |> Range.toSet) | |
Range.nonDivisible r1' r2 = Set.empty | |
testRange Div (r1'.Multiples |> Set.map int |> Set.toList) (r1'.Delta |> Option.get) | |
(r2.Multiples |> Set.map int |> Set.toList) (r2.Delta |> Option.get) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Note:
should probably be
to get all possible results. However is this needed in the context of GenSolver where:
r3 = r1 / r2
and for exampler3 = a * b
and botha
andb
are incremental? Thenr3
already has a fixed delta. In that case scaling shouldn't occur.So, scaling is only relevant when the result is still undetermined and there is no other way to calculate the delta for the result.