{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Julia is a modern dynamic language\n",
"\n",
" * sophisticated type system\n",
" * rich set of built-in types (numeric and general-purpose)\n",
" * user-defined types\n",
" * metaprogramming (macros)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Built-in numeric types\n",
"\n",
"Julia's built-in numeric types include a wide range of \n",
" * integers: Int16, Int32, Int64 (and unsigned ints), and arbitrary-precision BigInts \n",
" * floating-points: Float16, Float32, Float64, and arbitrary-precision BigFloats\n",
" * rationals using the integer types\n",
" * complex numbers formed from above\n",
" * vectors, matrices, linear algebra on above"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"π = 3.1415926535897..."
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"π"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"Irrational{:π}"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"typeof(π)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"3.141592653589793"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Float64(π)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"3.141592653589793238462643383279502884197169399375105820974944592307816406286198"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"pi = BigFloat(π)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"-1.000000000000000000000000000000000000000000000000000000000000000000000000000000 + 1.096917440979352076742130626395698021050758236508687951179005716992142688513354e-77im"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"exp(pi*1im)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"-1.0 + 1.2246467991473532e-16im"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"exp(π*1im)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"Complex{BigFloat}"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"typeof(ans)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"13176795//4194304"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Rational(Float32(pi))"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Float32(13176795 / 4194304) = 3.1415927f0\n",
"Float32(pi) = 3.1415927f0\n"
]
}
],
"source": [
"@show Float32(13176795/4194304);\n",
"@show Float32(pi);"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"5.0 + 3.0im"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"5.0 + 3im"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"Complex{Float64}"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"typeof(ans)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"5//3 - 7//9*im"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"5//3 + 7//9im"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"Complex{Rational{Int64}}"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"typeof(ans)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Introspection on Julia's numeric type hierarchy"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"2-element Array{Any,1}:\n",
" Complex{T<:Real}\n",
" Real "
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"subtypes(Number)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"4-element Array{Any,1}:\n",
" AbstractFloat \n",
" Integer \n",
" Irrational{sym} \n",
" Rational{T<:Integer}"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"subtypes(Real)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"4-element Array{Any,1}:\n",
" BigFloat\n",
" Float16 \n",
" Float32 \n",
" Float64 "
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"subtypes(AbstractFloat)"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"true"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Int32 <: Number # are Int64's numbers?"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"true"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Int64 <: Real # are Int64's a subset of the reals?"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"false"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Int64 <: Float64 # are Int64's a subset of 64-bit floating-point numbers?"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"false"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"17 ∈ 0:3:21 # is 17 an element of the set 0,3,6,9,12,15,18,21? (a set operation)"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"Bool"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"typeof(ans)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Solve a system of rational equations\n",
"\n",
"illustrates linear algebra over arbitrary-precision rationals"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"5x5 Array{Rational{BigInt},2}:\n",
" 2//5 9//10 4//5 3//5 4//5 \n",
" 3//10 1//1 4//5 1//10 3//5 \n",
" 3//10 1//2 3//10 7//10 3//10\n",
" 2//5 1//1 3//10 7//10 9//10\n",
" 1//2 1//10 4//5 3//5 3//10"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = convert(Matrix{Rational{BigInt}}, rand(1:10,5,5))/10"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"5-element Array{Rational{BigInt},1}:\n",
" 69052//13585 \n",
" 382199//65208 \n",
" 859823//326040\n",
" 229868//40755 \n",
" 177913//326040"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"x = [3//4; 17//3; -1//13; -7//11 ; 3//19]\n",
"b = A*x"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"5-element Array{Rational{BigInt},1}:\n",
" 3//4 \n",
" 17//3 \n",
" -1//13\n",
" -7//11\n",
" 3//19"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"x̂ = A\\b"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"5-element Array{Rational{BigInt},1}:\n",
" 0//1\n",
" 0//1\n",
" 0//1\n",
" 0//1\n",
" 0//1"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"x - x̂"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that Julia's backslash operator (and LU decomp) works over all its numeric types\n",
"\n",
"Float32 and Float64 LU, QR, SVD, etc. are calls to LAPACK"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Define a new numeric type: scalar finite field GF(p)\n",
"\n",
"example from Andreas Noack, CSAIL MIT http://andreasnoack.github.io/talks/2015AprilStanford_AndreasNoack.ipynb\n",
"\n",
"#### define scalar finite field GF(p) i.e. integers modulo p"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# Scalar finite fields. P is the modulus, T is the integer type (Int16, Int32, ...)\n",
"immutable GF{P,T<:Integer} <: Number\n",
" data::T\n",
" function GF(x::Integer)\n",
" return new(mod(x, P))\n",
" end\n",
"end"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" immutable: In Julia variables change values, but numbers do not."
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"show (generic function with 107 methods)"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# basic methods for scalar finite field\n",
"import Base: convert, inv, one, promote_rule, show, zero\n",
"\n",
"function call{P}(::Type{GF{P}}, x::Integer)\n",
" if !isprime(P)\n",
" throw(ArgumentError(\"P must be a prime\"))\n",
" end\n",
" return GF{P,typeof(x)}(mod(x, P))\n",
"end\n",
"convert{P,T}(::Type{GF{P,T}}, x::Integer) = GF{P}(x)\n",
"convert{P}(::Type{GF{P}}, x::Integer) = GF{P}(x)\n",
"convert{P,T}(::Type{GF{P,T}}, x::GF{P}) = GF{P,T}(x.data)\n",
"promote_rule{P,T1,T2<:Integer}(::Type{GF{P,T1}}, ::Type{T2}) = GF{P,promote_type(T1,T2\n",
")}\n",
"show(io::IO, x::GF) = show(io, x.data)"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
" #### Define basic arithmetic operations with metaprogramming\n"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import Base: +, -, *, /\n",
"\n",
"for op in (:+, :-, :*)\n",
" @eval begin\n",
" ($op){P,T}(x::GF{P,T}, y::GF{P,T}) = GF{P,T}($(op)(x.data, y.data))\n",
" end\n",
"end"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Create a couple variables of type GF(5) , do some arithmetic"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"x = 4\n",
"y = 3\n",
"x + y = 2\n",
"x - y = 1\n",
"x * y = 2\n"
]
}
],
"source": [
"x, y = GF{5}(9), GF{5}(8)\n",
"@show x\n",
"@show y\n",
"@show x + y\n",
"@show x - y\n",
"@show x * y\n",
";"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# Division requires slightly more care\n",
"function inv{P,T}(x::GF{P,T})\n",
" if x == zero(x)\n",
" throw(DivideError())\n",
" end\n",
" r, u, v = gcdx(x.data, P)\n",
" GF{P,T}(u)\n",
"end\n",
"(/){P}(x::GF{P}, y::GF{P}) = x*inv(y)\n",
";"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"x / y = 3\n",
"x \\ y = 2\n"
]
}
],
"source": [
"@show x / y\n",
"@show x \\ y # backslash on any Number is defined in terms of /, so we get it autmomatically\n",
";"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### With the field operations defined, we can now do linear algebra"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"4x4 Array{GF{5,Int64},2}:\n",
" 3 1 1 0\n",
" 1 3 4 3\n",
" 4 3 2 2\n",
" 0 0 1 1"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# create 4x4 matrix of random GF(5) elems\n",
"srand(1234)\n",
"A = [GF{5}(rand(0:4)) for i = 1:4, j = 1:4] "
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"4-element Array{GF{5,Int64},1}:\n",
" 4\n",
" 1\n",
" 2\n",
" 0"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"b = [GF{5}(rand(0:4)) for i = 1:4]"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"4-element Array{GF{5,Int64},1}:\n",
" 2\n",
" 3\n",
" 0\n",
" 0"
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"x = A\\b"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### Whoa! The built-in matrix backslash works because the generic Julia LU decomp code works over any field"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"4-element Array{GF{5,Int64},1}:\n",
" 0\n",
" 0\n",
" 0\n",
" 0"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A*x - b"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"Array{GF{5,Int64},1}"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"typeof(x)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"methods(+)"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"+(A::AbstractArray{T,N}, x::Number) at arraymath.jl:139"
],
"text/plain": [
"+(A::AbstractArray{T,N}, x::Number) at arraymath.jl:139"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"@which x + y"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"+{P,T}(x::GF{P,T}, y::GF{P,T}) at In[30]:5"
],
"text/plain": [
"+{P,T}(x::GF{P,T}, y::GF{P,T}) at In[30]:5"
]
},
"execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"@which GF{7}(4) + GF{7}(1)"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"+(x::Int64, y::Int64) at int.jl:8"
],
"text/plain": [
"+(x::Int64, y::Int64) at int.jl:8"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"@which 4+8"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Compare computational costs of GF(p) to Float64 \n",
"\n",
"matrix-matrix mult "
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"int mat mult 0.001053 seconds (157 allocations: 88.651 KB)\n",
"GF(p) mat mult 0.009569 seconds (13 allocations: 78.656 KB)\n"
]
}
],
"source": [
"A1, A2 = rand(1:100, 100, 100), rand(1:100, 100, 100)\n",
"A1*A2 # warm up to be sure function is compiled\n",
"print(\"int mat mult \")\n",
"@time A1*A2\n",
"\n",
"AF1, AF2 = map(GF{5}, A1), map(GF{5}, A2)\n",
"AF1*AF2\n",
"print(\"GF(p) mat mult \")\n",
"@time AF1*AF2\n",
";"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"LU factorization: Float64 via LAPACK, GF(p) via generic LU algorithm"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Float64 mat lufact 0.000415 seconds (8 allocations: 79.250 KB)\n",
"GF(p) mat lufact 0.004178 seconds (8 allocations: 79.250 KB)\n"
]
}
],
"source": [
"lufact(A1)\n",
"print(\"Float64 mat lufact \")\n",
"\n",
"@time lufact(A1) # Promoted to Float64 and calls LAPACK\n",
"\n",
"F = lufact(AF1,Val{false})\n",
"while F.info != 0\n",
" AF1[F.info, F.info] += 1\n",
" F = lufact(AF1, Val{false})\n",
"end\n",
"\n",
"lufact(AF1)\n",
"print(\"GF(p) mat lufact \")\n",
"@time lufact(AF1) # Non-blocked generic LU implemented in Julia\n",
";"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### According to Noack, the increased cost of GF(p) over floats is just the modulus operations "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### maybe show symbolic mathematics in Noack's notebook..."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Julia 0.4.5",
"language": "julia",
"name": "julia-0.4"
},
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "0.4.5"
}
},
"nbformat": 4,
"nbformat_minor": 2
}