Skip to content

Instantly share code, notes, and snippets.

@ninegrid
Created May 22, 2014 07:56
Show Gist options
  • Save ninegrid/972aa47c91ec8be1b749 to your computer and use it in GitHub Desktop.
Save ninegrid/972aa47c91ec8be1b749 to your computer and use it in GitHub Desktop.
// Learn more about F# at http://fsharp.net
namespace BasicConcepts
module Algorithms =
let ``1.1E`` (m : uint32) (n : uint32) =
let rec aux m n l =
let r = m % n
if r <> 0u then aux n r (r :: l) else l
aux m n [] |> Seq.head
open Algorithms
//module Tests =
// do ``1.1E`` 119u 544u |> ignore
module Excersizes =
let ``1.1_1[10]`` a b c d =
let mutable a' = a
let mutable b' = b
let mutable c' = c
let mutable d' = d
let mutable t = a
a' <- b
b' <- c
c' <- d
d' <- t
(a,b,c,d)
let ``1.1_2[15]`` (m : uint32) (n : uint32) =
(m % n, n % m)
let ``1.1_3[20]`` m n =
let ``1.1F`` (m : uint32) (n : uint32) =
let rec aux m n l =
if m < n then aux n m l
else
let r = m % n
if r <> 0u then aux n r (r :: l) else l
aux m n [] |> Seq.head in
``1.1F`` m n
let ``1.1_4[16]`` = ``1.1_3[20]`` 2166u 6099u
let ``1.1_5[12]`` = () (* regarding the algorithm for reading the book and not applicable to code *)
let ``1.1_6[20]`` =
let commonDivisors (m : uint32) (n : uint32) =
let rec aux m n l =
let r = m % n
let l' = r :: l
if r <> 0u then aux n r l' else l
aux m n []
seq { for i in 1u..100000u do yield! [commonDivisors i 5u] }
|> Seq.map (fun xs -> float (Seq.length xs) + 1.)
|> Seq.average
let ``1.1_7[M21]`` =
let commonDivisors (m : uint32) (n : uint32) =
let rec aux m n l =
let r = m % n
let l' = r :: l
if r <> 0u then aux n r l' else l
aux m n []
seq { for i in 1u..100000u do yield! [commonDivisors 5u i] }
|> Seq.map (fun xs -> float (Seq.length xs) + 1.)
|> Seq.average
let ``1.1_8[M25]`` = () (* hard *)
let ``1.1_9[M30]`` = () (* hard *)
namespace BasicConcepts
module Algorithms =
/// <summary>Euclid's Algorithm</summary>
/// <remarks>
/// Given two positive integers m and n, find their greatest common divisor, that is, the largest positive
/// integer that evenly divides both m and n.
/// </remarks>
/// <typeparam name="m"></typeparam>
/// <typeparam name="n"></typeparam>
/// <returns>uint32</returns>
val ``1.1E`` : uint32 -> uint32 -> uint32

// Learn more about F# at http://fsharp.net
namespace BasicConcepts
module Algorithms =
let ``1.1E`` (m : uint32) (n : uint32) =
let rec aux m n l =
let r = m % n
if r <> 0u then aux n r (r :: l) else l
aux m n [] |> Seq.head
open Algorithms
//module Tests =
// do ``1.1E`` 119u 544u |> ignore
module Excersizes =
let ``1.1_1[10]`` a b c d =
let mutable a' = a
let mutable b' = b
let mutable c' = c
let mutable d' = d
let mutable t = a
a' <- b
b' <- c
c' <- d
d' <- t
(a,b,c,d)
let ``1.1_2[15]`` (m : uint32) (n : uint32) =
(m % n, n % m)
let ``1.1_3[20]`` m n =
let ``1.1F`` (m : uint32) (n : uint32) =
let rec aux m n l =
if m < n then aux n m l
else
let r = m % n
if r <> 0u then aux n r (r :: l) else l
aux m n [] |> Seq.head in
``1.1F`` m n
let ``1.1_4[16]`` = ``1.1_3[20]`` 2166u 6099u
let ``1.1_5[12]`` = () (* regarding the algorithm for reading the book and not applicable to code *)
let ``1.1_6[20]`` =
let commonDivisors (m : uint32) (n : uint32) =
let rec aux m n l =
let r = m % n
let l' = r :: l
if r <> 0u then aux n r l' else l
aux m n []
seq { for i in 1u..100000u do yield! [commonDivisors i 5u] }
|> Seq.map (fun xs -> float (Seq.length xs) + 1.)
|> Seq.average
let ``1.1_7[M21]`` =
let commonDivisors (m : uint32) (n : uint32) =
let rec aux m n l =
let r = m % n
let l' = r :: l
if r <> 0u then aux n r l' else l
aux m n []
seq { for i in 1u..100000u do yield! [commonDivisors 5u i] }
|> Seq.map (fun xs -> float (Seq.length xs) + 1.)
|> Seq.average
let ``1.1_8[M25]`` = () (* hard *)
let ``1.1_9[M30]`` = () (* hard *)
namespace BasicConcepts
module MathematicalPreliminaries =
let ``1.2.1I`` (P : int -> bool) (n : int) =
seq [ 1 .. n + 1 ] |> Seq.tryPick (fun k -> if P k then None else Some(k))
let ``1.2.1E`` (m : int) (n : int) =
let rec aux a' a b' b c d m n =
let q = c / d
let r = c % d
if r = 0 then printfn "%A" (a',a,b',b,c,d,q,r); (a',a,b',b,c,d,q,r)
else
printfn "%A" (a',a,b',b,c,d,q,r)
aux a (a'-(q*a)) b (b'-(q*b)) d r m n
aux 1 0 0 1 m n m n
open MathematicalPreliminaries
module Tests =
let induct = ``1.2.1I``
let ``1.2.1.Eq. (2)`` n =
let x = float n
if Seq.reduce (+) [1. .. 2. .. (2.*x) - 1.] = x ** 2. then true else false
let t0 = induct ``1.2.1.Eq. (2)`` 10
let fibs = Seq.unfold (fun (n0, n1) -> Some(n0, (n1, n0+n1))) (0I,1I)
let phi = (1. + (sqrt 5.)) / 2.
let ``1.2.1.Eq. (3)`` n =
if (float (Seq.nth n fibs) <= (phi ** (float (n - 1)))) then true else false
let t1 = induct ``1.2.1.Eq. (3)`` 10
(* learn to do ``1.2.1.Eq (4)`` *)
let ``1.2.1.Eq. (5)`` = (1. + phi = phi ** 2.)
let t2 = ``1.2.1E`` 1000000 10000000
let ``1.2.1.Eq (6)`` =
let m = 1769
let n = 551
match ``1.2.1E`` m n with
| (a',a,b',b,c,d,q,r) -> if (((a' * m) + (b' * n) = c)
&& ((a * m) + (b * n) = d)) then true else false
module Excersizes =
let ``1.2.1.Ex.1[05]`` = ()
let ``1.2.1.Ex.2[15]`` = ()
let ``1.2.1.Ex.3[18]`` = ()
let ``1.2.1.Ex.4[20]`` = ()
let ``1.2.1.Ex.5[21]`` = ()
let ``1.2.1.Ex.6[20]`` = ()
let ``1.2.1.Ex.7[23]`` = ()
let ``1.2.1.Ex.8[25]`` = ()
let ``1.2.1.Ex.9[20]`` = ()
let ``1.2.1.Ex.10[M22]`` = ()
let ``1.2.1.Ex.11[M30]`` = ()
let ``1.2.1.Ex.12[M25]`` = ()
let ``1.2.1.Ex.13[M23]`` = ()
let ``1.2.1.Ex.14[50]`` = ()
let ``1.2.1.Ex.15[HM28]`` = ()
namespace BasicConcepts
module MathematicalPreliminaries =
val ``1.2.1I`` : (int -> bool) -> int -> int option
namespace BasicConcepts
module MathematicalPreliminaries =
let ``1.2.1I`` (P : int -> bool) (n : int) =
seq [ 1 .. n + 1 ] |> Seq.tryPick (fun k -> if P k then None else Some(k))
let ``1.2.1E`` (m : int) (n : int) =
let rec aux a' a b' b c d m n =
let q = c / d
let r = c % d
if r = 0 then printfn "%A" (a',a,b',b,c,d,q,r); (a',a,b',b,c,d,q,r)
else
printfn "%A" (a',a,b',b,c,d,q,r)
aux a (a'-(q*a)) b (b'-(q*b)) d r m n
aux 1 0 0 1 m n m n
open MathematicalPreliminaries
module Tests =
let induct = ``1.2.1I``
let ``1.2.1.Eq. (2)`` n =
let x = float n
if Seq.reduce (+) [1. .. 2. .. (2.*x) - 1.] = x ** 2. then true else false
let t0 = induct ``1.2.1.Eq. (2)`` 10
let fibs = Seq.unfold (fun (n0, n1) -> Some(n0, (n1, n0+n1))) (0I,1I)
let phi = (1. + (sqrt 5.)) / 2.
let ``1.2.1.Eq. (3)`` n =
if (float (Seq.nth n fibs) <= (phi ** (float (n - 1)))) then true else false
let t1 = induct ``1.2.1.Eq. (3)`` 10
(* learn to do ``1.2.1.Eq (4)`` *)
let ``1.2.1.Eq. (5)`` = (1. + phi = phi ** 2.)
let t2 = ``1.2.1E`` 1000000 10000000
let ``1.2.1.Eq (6)`` =
let m = 1769
let n = 551
match ``1.2.1E`` m n with
| (a',a,b',b,c,d,q,r) -> if (((a' * m) + (b' * n) = c)
&& ((a * m) + (b * n) = d)) then true else false
module Excersizes =
let ``1.2.1.Ex.1[05]`` = ()
let ``1.2.1.Ex.2[15]`` = ()
let ``1.2.1.Ex.3[18]`` = ()
let ``1.2.1.Ex.4[20]`` = ()
let ``1.2.1.Ex.5[21]`` = ()
let ``1.2.1.Ex.6[20]`` = ()
let ``1.2.1.Ex.7[23]`` = ()
let ``1.2.1.Ex.8[25]`` = ()
let ``1.2.1.Ex.9[20]`` = ()
let ``1.2.1.Ex.10[M22]`` = ()
let ``1.2.1.Ex.11[M30]`` = ()
let ``1.2.1.Ex.12[M25]`` = ()
let ``1.2.1.Ex.13[M23]`` = ()
let ``1.2.1.Ex.14[50]`` = ()
let ``1.2.1.Ex.15[HM28]`` = ()

#r "FSharp.PowerPack.dll"
module LazyListIntegerPartitionDelayed =
exception Subscript
type Partition = int LazyList
type CompressedPartition = int * Partition
(* val expand : CompressedPartition -> Partition *)
let rec expand (p : CompressedPartition) =
match p with
| 0,p -> p
| n,p -> (expand ((n-1), LazyList.consDelayed 1 (fun () -> p)))
(* val pack : int -> CompressedPartition -> CompressedPartition *)
let rec pack (n : int) (cp : CompressedPartition) =
match n with
| 1 -> cp
| k -> if k > (fst cp) then pack (k-1) (cp)
else pack k (((fst cp) - k), LazyList.consDelayed k (fun () -> (snd cp)))
(* val nextpartition : CompressedPartition -> CompressedPartition *)
let nextPartition (cp : CompressedPartition) =
match cp with
| k,LazyList.Cons(x,xs) -> pack (x-1) ((k+x),xs)
| k,LazyList.Nil -> raise Subscript
let rev (xs : LazyList< 'a >) : LazyList< 'a > =
let rec loop xs ys =
match xs with
LazyList.Nil -> ys
| LazyList.Cons(x, xs) -> loop xs (LazyList.consDelayed x (fun () -> ys))
loop xs LazyList.empty
(* val generatePs : CompressedPartition -> Partition list *)
let generatePartitions (cp : CompressedPartition) =
let rec loop (cp : CompressedPartition) rs =
match cp with
| n,LazyList.Nil -> (LazyList.cons (rev (expand cp)) rs)
| n,LazyList.Cons(x,xs) -> loop (nextPartition cp) (LazyList.consDelayed (rev (expand cp)) (fun () -> rs))
loop cp LazyList.empty
(* val part : int -> Partition list *)
let rec part n (lexicographic : bool) =
match lexicographic with
| false -> part n (true) |> rev
| true -> match n with
| n when n < 1 -> raise Subscript
| n when n = 1 -> LazyList.consDelayed (LazyList.ofList [1]) (fun () -> (LazyList.empty))
| _ -> generatePartitions (0,(LazyList.ofList [n]))
open LazyListIntegerPartitionDelayed
#time
part 60 true
(* Notes for making it tail-recursive. *)
(* naive implementation not tail recursive *)
let rec count n =
match n with
0 -> []
| n -> n :: count (n - 1)
(* ^
|.... the cons operator is in the tail position
as such, it is evaluated last, so this drags
the stack through all recursive calls *)
(* apply continuation passing style with parameterized function *)
let count' n =
let rec count n ret =
match n with
0 -> ret [] (* v------ this is continuation passing style *)
| n -> count (n - 1) (fun cs -> n :: cs)
(* ^
|... the recursive call is now in tail position *)
count n (fun cs -> cs)
(* refactor the parameterized function into a specialized representation
this is an optimization of the second example. if you have something
like the first example and you can't figure out how to make it tail
recursive, what I'm suggesting is that you write the second one and
then try to optimize it to eliminate the function parameter
-- TheOnionKnight *)
let count'' n =
let rec count n ret =
match n with
0 -> List.rev ret
| n -> count (n - 1) (n :: ret)
count n []
count 20
count' 20
count'' 20

let (|Even|Odd|) n = if n%2 = 0 then Even else Odd
let P1 n =
match n * (n + 3) with
| Even -> true
| Odd -> false
let P2 n =
if n >= 10 then
let x = float n
if 2. ** x > x ** 3. then true else false
else true
let P3 n =
let x = float n
if 2.*(x - 1.) = x ** 2. then true else false
// implement algorithm I for these proposition functions on your own
open System
open System.Collections.Generic
let induct prop (s : IEnumerable<_>) = Seq.tryPick (fun x -> if prop (x+1) then None
else Some(x)) (Seq.append (seq [-1]) s)
induct P1 [0 .. 1000]
induct P2 [0 .. 1000]
#time
let fibs = Seq.unfold (fun (n0, n1) -> Some(n0, (n1, n0+n1))) (0I,1I)
fibs |> Seq.nth 45
let phi = (1. + (sqrt 5.)) / 2.
(1. + phi = phi ** 2.)
let P4 n =
if (float (Seq.nth n fibs) <= (phi ** (float (n - 1)))) then true else false
induct P4 [0]
P4 0
Seq.nth 0 fibs
let nthroot n a =
let epsilon_float = 2.2204460492503131e-16m
let nf = float n in
let x = [| a; a / nf |] in
while System.Math.Abs(x.[1] - x.[0]) > epsilon_float do
x.[0] <- x.[1];
x.[1] <- ((nf - 1.0) * x.[1] + a / (x.[1] ** (nf - 1.0))) / nf;
x.[1]
let phiM = (1.m + (nthroot 5.m 2) / 2.m)
phi
namespace BasicConcepts
module NumbersPowersLogarithms =
let x = ()
open NumbersPowersLogarithms
module Tests =
(* not all equations are suitable for code *)
let integer = 1
let rational = 1N/2N (* requires powerpack *)
let real = 1.123456789
let real' = 0.99999999999 (* equals 1 *)
let y = ()

namespace BasicConcepts
#r "FSharp.PowerPack.dll"
module NumbersPowersLogarithms =
let x = ()
open NumbersPowersLogarithms
module Tests =
(* not all equations are suitable for code *)
let integer = 1
let rational = 1N/2N
let real = 1.123456789
let real' = 0.99999999999 (* equals 1 *)
let y = ()
open System
let r = new System.Random()
let roll () = (r.Next() % 5) + 1
let rolls = seq { for x in 1 .. 144 do yield seq { for x in 1 .. 144 do yield (roll(),roll()) }}
rolls |> Seq.take 2
rolls |> Seq.map (fun xs -> Seq.map (fun x -> fst x + snd x) xs)
<?xml version="1.0" encoding="utf-8"?>
<Project ToolsVersion="4.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
<PropertyGroup>
<Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
<Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
<ProductVersion>8.0.30703</ProductVersion>
<SchemaVersion>2.0</SchemaVersion>
<ProjectGuid>{3c9762e2-3a83-4dfd-a7ac-663c17a40df7}</ProjectGuid>
<OutputType>Library</OutputType>
<RootNamespace>AoCP</RootNamespace>
<AssemblyName>AoCP</AssemblyName>
<TargetFrameworkVersion>v4.0</TargetFrameworkVersion>
<Name>AoCP</Name>
</PropertyGroup>
<PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
<DebugSymbols>true</DebugSymbols>
<DebugType>full</DebugType>
<Optimize>false</Optimize>
<Tailcalls>false</Tailcalls>
<OutputPath>bin\Debug\</OutputPath>
<DefineConstants>DEBUG;TRACE</DefineConstants>
<WarningLevel>3</WarningLevel>
<DocumentationFile>bin\Debug\AoCP.XML</DocumentationFile>
</PropertyGroup>
<PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
<DebugType>pdbonly</DebugType>
<Optimize>true</Optimize>
<Tailcalls>true</Tailcalls>
<OutputPath>bin\Release\</OutputPath>
<DefineConstants>TRACE</DefineConstants>
<WarningLevel>3</WarningLevel>
<DocumentationFile>bin\Release\AoCP.XML</DocumentationFile>
</PropertyGroup>
<Import Project="$(MSBuildExtensionsPath32)\FSharp\1.0\Microsoft.FSharp.Targets" Condition="!Exists('$(MSBuildBinPath)\Microsoft.Build.Tasks.v4.0.dll')" />
<Import Project="$(MSBuildExtensionsPath32)\..\Microsoft F#\v4.0\Microsoft.FSharp.Targets" Condition=" Exists('$(MSBuildBinPath)\Microsoft.Build.Tasks.v4.0.dll')" />
<ItemGroup>
<Compile Include="1.1.fsi" />
<Compile Include="1.1.fs" />
<None Include="1.1.fsx" />
<None Include="1.1_usage.fsx" />
<Compile Include="1.2.1.fsi" />
<Compile Include="1.2.1.fs" />
<None Include="1.2.1.fsx" />
<None Include="1.2.1_usage.fsx" />
<None Include="1.2.1_Digression_IntegerPartition_TailRecursion.fsx" />
<None Include="1.2.2.fsx" />
<None Include="1.2.2_usage.fsx" />
<None Include="3.3.1.fsx" />
</ItemGroup>
<ItemGroup>
<Reference Include="mscorlib" />
<Reference Include="FSharp.Core" />
<Reference Include="System" />
<Reference Include="System.Core" />
<Reference Include="System.Numerics" />
</ItemGroup>
<!-- To modify your build process, add your task inside one of the targets below and uncomment it.
Other similar extension points exist, see Microsoft.Common.targets.
<Target Name="BeforeBuild">
</Target>
<Target Name="AfterBuild">
</Target>
-->
</Project>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment