nestordemeure

/*
Most people use Kahan summation[0] when they want a higher precision sum.
Mostly because it is the only thing they know.

Here is an alternative that is:
- almost as fast (while having no unpredictable branch), 
- significantly more precise (about as precise as doubling the floating point precision with added resilience to cancelations)
- very easy to implement in your favorite programming language.

For more information, I highly recommend reading the Handbook of floating-point arithmetic.

nestordemeure

library(magrittr)
library(pwr)

#------------------------------------------------------------------------------
# probability of error computation

# estimate beta for a t-test with inequal nb_ko and nb_wt
# see https://www.statmethods.net/stats/power.html
# use formulas from Cohen 1988 http://www.utstat.toronto.edu/~brunner/oldclass/378f16/readings/CohenPower.pdf
compute_beta <- function(alpha, nb_ko, nb_wt, effect_size)

nestordemeure

# Rust format configuration file
# https://github.com/rust-lang/rustfmt/blob/master/Configurations.md
indent_style = "Visual"
control_brace_style = "AlwaysNextLine"
use_small_heuristics = "Max"
brace_style = "AlwaysNextLine"
where_single_line = true
imports_indent = "Visual"
trailing_comma = "Never"
overflow_delimited_expr = true

nestordemeure

open System.Collections.Generic

type Tree = { Value : int; Children : Tree Set }

//-------------------------------------------------------------------------------------------------

/// get the primary key from a node
/// placeholder : if the value cannot be used as a primary key, this bit should be changed
let getKey tree = 

nestordemeure

// 3D surface example with Xplot.Plotly
// examples appears to be outdated but they can be completed using the git

#load "packages/FsLab/FsLab.fsx"

open System
open XPlot.Plotly

// matrix included in the git but not on the main page

nestordemeure

/// builds 3 towers with the given number of disks in the first tower
let towers diskNumber = [| [1 .. diskNumber]; []; [] |]

//-------------------------------------------------------------------------------------------------
// RECURSIVE SOLUTION

/// moves the top disks in fromTower onto toTower
/// displays the move and the result 
/// checks if the move is legal

nestordemeure

(* 
   The Xorshift128+ generator generates a high-quality 64-bit value very quickly (see reference). 
   It is presently used in the JavaScript engines of Chrome, Firefox and Safari, and it is the default generator in Erlang. 
   If you find its period too short for large-scale parallel simulations, use xorshift1024*.

   Note that the lowest bit of this generator is an LSFR, 
   and thus it is slightly less random than the other bits. 
   We suggest to use a sign test to extract a random Boolean value.

   Reference : http://xoroshiro.di.unimi.it/

nestordemeure

/// compute the minimum of 3 elements
let min3 a b c = if a < b then min a c else min b c 

/// compute the levenstein distance between two strings given the substitution/deletion/insertion cost
let levenstein sub del ins (s1:string) (s2:string) =
    // arrays to store the previous results
    let cost = Array.init (s1.Length+1) id 
    let mutable costPrev = 0 // contains the content of cost.[i1-1] during the previous iteration
    // main loop on all pairs of characters
    for i2 = 1 to s2.Length do 

nestordemeure

// PAIRING HEAP : AMORTIZED MIN PRIORITY QUEUE

/// struct to store a value and its key (cache friendly)
type HeapEntry<'K,'V> = struct val k:'K val v:'V new(k,v) = {k=k;v=v} end

/// good amortized Min Priority Queue
/// the price of a deleteMin/popMin can go up to O(n) but it is amortizd into O(ln(n)) other operations are O(1)
type PairingHeap<'K,'V> =
    | EmptyHeap
    | Heap of HeapEntry<'K,'V> * (PairingHeap<'K,'V> list)

nestordemeure

// KNAPSACK

/// weight should be minimised and price maximised
type Object = {weight : int ; price : int ; id : int}
type State = {weight : int ; price : int ; objects : Object list}
let emptyState = {weight=0 ; price=0 ; objects=[]} 

/// returns a list of object wich maximise the price while keeping sum(weight) <= maxWeight
/// solution using dynamic programming
/// might explode if maxWeight gets too big : can be avoided by dividing the weights (aproximate solution)