You can view this notebook by running a web server in this directory and visiting it as a webpage. For example:
python -m SimpleHTTPServer
# Then, visit http://localhost:8000.Or, use the Notebook Runtime API to integrate directly with lattice-reduction.js, which contains the notebook compiled as an ES module.
Exported from version 212 of Lattice reduction on observablehq.com.
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <title>Lattice reduction</title> | |
| <link rel="stylesheet" type="text/css" href="https://unpkg.com/@observablehq/notebook-inspector@1/dist/notebook-inspector-style.css"> | |
| <body> | |
| <script type="module"> | |
| import {Inspector, Runtime} from "https://unpkg.com/@observablehq/notebook-runtime@1?module"; | |
| import notebook from "./lattice-reduction.js"; | |
| Runtime.load(notebook, Inspector.into(document.body)); | |
| </script> |
| // URL: https://beta.observablehq.com/@bryangingechen/lattice-reduction | |
| // Title: Lattice reduction | |
| // Author: Bryan Gin-ge Chen (@bryangingechen) | |
| // Version: 212 | |
| // Runtime version: 1 | |
| const m0 = { | |
| id: "0d0d4e55f05ea8aa@212", | |
| variables: [ | |
| { | |
| inputs: ["md"], | |
| value: (function(md){return( | |
| md`# Lattice reduction` | |
| )}) | |
| }, | |
| { | |
| inputs: ["md","lilDot","tex","pic"], | |
| value: (function(md,lilDot,tex,pic){return( | |
| md`Lattice basis vectors (in pixels):<br> | |
| ${lilDot('rgba(128,255,128,1)')} ${tex`\vec{a}=(${pic.lattice.ax.toPrecision(4)},${pic.lattice.ay.toPrecision(4)})`},<br> | |
| ${lilDot('rgba(128,128,255,1)')} ${tex`\vec{b}=(${pic.lattice.bx.toPrecision(4)},${pic.lattice.by.toPrecision(4)})`}. | |
| Drag these two dots below to modify the basis vectors, or drag anywhere else to rotate / zoom. After releasing, the lattice basis is [reduced](https://en.wikipedia.org/wiki/Lattice_reduction), resulting in an equivalent, but shorter basis. | |
| *Algorithm used here taken from Chapter 17 of Steven Galbraith's book ["Mathematics of Public Key Cryptography"](https://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html).*` | |
| )}) | |
| }, | |
| { | |
| inputs: ["html","viewof pic"], | |
| value: (function(html,$0) | |
| { | |
| const div = html`<div>`; | |
| const resetButton = html`<button>Randomize lattice`; | |
| resetButton.onclick = () => { | |
| $0.dispatchEvent(new CustomEvent('reset')); | |
| }; | |
| div.appendChild(resetButton); | |
| const squareButton = html`<button>Square lattice`; | |
| squareButton.onclick = () => { | |
| $0.dispatchEvent(new CustomEvent('square')); | |
| }; | |
| div.appendChild(squareButton); | |
| const triButton = html`<button>Triangular lattice`; | |
| triButton.onclick = () => { | |
| $0.dispatchEvent(new CustomEvent('triangular')); | |
| }; | |
| div.appendChild(triButton); | |
| return div; | |
| } | |
| ) | |
| }, | |
| { | |
| name: "viewof pic", | |
| inputs: ["DOM","width","height","reduceBasis","getParticles","object","renderVoronoi","renderLattice","renderBasis","renderTextLattice","d3","invalidation"], | |
| value: (function(DOM,width,height,reduceBasis,getParticles,object,renderVoronoi,renderLattice,renderBasis,renderTextLattice,d3,invalidation) | |
| { | |
| const SQRT3_2 = Math.sqrt(3)/2; | |
| const context = DOM.context2d(width, height); | |
| const frames = new Map(); | |
| function initLattice() { | |
| const ax = Math.random()*100; | |
| const ay = Math.random()*100; | |
| const bx = Math.random()*100; | |
| const by = Math.random()*100; | |
| const latt = ({ax,ay,bx,by}); | |
| [[latt.ax,latt.ay], [latt.bx,latt.by]] = reduceBasis([ax,ay],[bx,by]); | |
| const n = Math.min(height,width)/Math.max(Math.abs(latt.ax),Math.abs(latt.ay), | |
| Math.abs(latt.bx),Math.abs(latt.by)) / 4; | |
| latt.ax *= n; | |
| latt.ay *= n; | |
| latt.bx *= n; | |
| latt.by *= n; | |
| return latt; | |
| } | |
| let state = this ? this.value.state : ({}); | |
| let lattice = this ? this.value.lattice : initLattice(); | |
| function render(context, state, lattice) { | |
| context.fillStyle = `#333`; | |
| context.fillRect(0, 0, width, height); | |
| state.particles = getParticles(object.m, object.n, lattice); | |
| renderVoronoi(context, state, lattice); | |
| renderLattice(context, state); | |
| renderBasis(context, lattice, state.clicked); | |
| const {ax,ay,bx,by} = lattice; | |
| const fontSize = Math.min(20, Math.sqrt(ax*ax+ay*ay)/3, Math.sqrt(bx*bx+by*by)/3); | |
| if (object.labelPoints) | |
| renderTextLattice(context, state, {textFunc:({i,j}) => `(${j},${i})`, fontSize, shift:fontSize*3/2}); | |
| context.canvas.value = {state, lattice}; | |
| context.canvas.dispatchEvent(new CustomEvent('input')); | |
| } | |
| function testDist(x1,y1,x2,y2,r) { | |
| const dx = x1-x2; | |
| const dy = y1-y2; | |
| const dist = dx*dx+dy*dy; | |
| return dist < r*r; | |
| } | |
| function dragSubject() { | |
| const {x,y} = d3.event; | |
| const x0 = x - width/2; | |
| const y0 = height/2 - y; | |
| const dd0 = x0*x0 + y0*y0; | |
| const ang0 = Math.atan2(y0,x0); | |
| const {ax,ay,bx,by} = lattice; | |
| let type; | |
| if (testDist(x0,y0, ax,ay, 8)) { | |
| state.clicked = type = 'a'; // lattice vector a | |
| renderBasis(context, lattice, 'a'); | |
| } else if (testDist(x0,y0, bx,by, 8)) { | |
| state.clicked = type = 'b'; // lattice vector b | |
| renderBasis(context, lattice, 'b'); | |
| } else type = 'B'; // background | |
| return {type, dd0,ang0, ax,ay,bx,by}; | |
| } | |
| function dragged() { | |
| const {x,y, subject:{type, dd0,ang0, ax,ay,bx,by}} = d3.event; | |
| const x1 = x - width/2; | |
| const y1 = height/2 - y; | |
| switch (type) { | |
| case 'a': { | |
| lattice.ax = x1; | |
| lattice.ay = y1; | |
| break; | |
| } | |
| case 'b': { | |
| lattice.bx = x1; | |
| lattice.by = y1; | |
| break; | |
| } | |
| case 'B': { | |
| // zoom and rotate | |
| const ang = Math.atan2(y1,x1); | |
| const scale = Math.sqrt((x1*x1 + y1*y1) / dd0); | |
| const c = Math.cos(ang-ang0); | |
| const s = Math.sin(ang-ang0); | |
| lattice.ax = scale*(c*ax - s*ay); | |
| lattice.ay = scale*(s*ax + c*ay); | |
| lattice.bx = scale*(c*bx - s*by); | |
| lattice.by = scale*(s*bx + c*by); | |
| break; | |
| } | |
| } | |
| render(context, state, lattice); | |
| } | |
| function dragEnd() { | |
| const {ax,ay,bx,by} = lattice; | |
| [[lattice.ax,lattice.ay], [lattice.bx,lattice.by]] = reduceBasis([ax,ay],[bx,by]); | |
| state.clicked = null; | |
| render(context, state, lattice); | |
| } | |
| d3.select(context.canvas).call( | |
| d3.drag().subject(dragSubject) | |
| .on("drag", dragged) | |
| .on("end", dragEnd) | |
| ); | |
| function tick(it, f, key) { | |
| render(context, state, lattice = it(d3.easeCubic(f / 90))); | |
| if (f < 90) | |
| frames.set(key, requestAnimationFrame(() => tick(it,f,key))); | |
| f++; | |
| } | |
| function cancelAll() { | |
| for (const frame of frames) | |
| cancelAnimationFrame(frame); | |
| } | |
| context.canvas.addEventListener('reset', () => { | |
| cancelAll(); | |
| const finLattice = initLattice(); | |
| const it = d3.interpolate(lattice, finLattice); | |
| let f = 0; | |
| tick(it, f, 'reset'); | |
| }); | |
| context.canvas.addEventListener('square', () => { | |
| cancelAll(); | |
| const finLattice = Object.assign({}, lattice); | |
| finLattice.bx = -lattice.ay; | |
| finLattice.by = lattice.ax; | |
| const it = d3.interpolate(lattice, finLattice); | |
| let f = 0; | |
| tick(it, f, 'square'); | |
| }); | |
| context.canvas.addEventListener('triangular', () => { | |
| cancelAll(); | |
| const finLattice = Object.assign({}, lattice); | |
| finLattice.bx = lattice.ax/2 - lattice.ay*SQRT3_2; | |
| finLattice.by = SQRT3_2*lattice.ax + lattice.ay/2; | |
| const it = d3.interpolate(lattice, finLattice); | |
| let f = 0; | |
| tick(it, f, 'triangular'); | |
| }); | |
| render(context, state, lattice); | |
| invalidation.then(cancelAll); | |
| return context.canvas; | |
| } | |
| ) | |
| }, | |
| { | |
| name: "pic", | |
| inputs: ["Generators","viewof pic"], | |
| value: (G, _) => G.input(_) | |
| }, | |
| { | |
| name: "viewof object", | |
| inputs: ["form","html","tex","md"], | |
| value: (function(form,html,tex,md) | |
| { | |
| const div = form(html`<form> | |
| <div> | |
| <label><input type="number" name="m" min="1" max="100" value="15" style="width:50px" /> half-width in ${tex`\vec{a}`}-direction.</label><br> | |
| <label><input type="number" name="n" min="1" max="100" value="15" style="width:50px" /> half-width in ${tex`\vec{b}`}-direction.</label> | |
| </div> | |
| <label><input type="checkbox" name="labelPoints" checked /> label lattice points</label> | |
| </div> | |
| <figcaption>${md`Sometimes the Voronoi cells show spurious lines. Sorry about that. See [this Delaunator issue](https://github.com/mapbox/delaunator/issues/43).`}</figcaption> | |
| </form>`); | |
| div.addEventListener('uncheck', () => { | |
| div.m.valueAsNumber = 15; | |
| div.n.valueAsNumber = 15; | |
| div.labelPoints.checked = true; | |
| div.dispatchEvent(new CustomEvent('input')); | |
| }); | |
| return div; | |
| } | |
| ) | |
| }, | |
| { | |
| name: "object", | |
| inputs: ["Generators","viewof object"], | |
| value: (G, _) => G.input(_) | |
| }, | |
| { | |
| inputs: ["md"], | |
| value: (function(md){return( | |
| md`**See also:** I stole some tricks from Mike Bostock's ["Regular plane tilings"](/@mbostock/regular-plane-tilings/2) in the update of this notebook, namely, using [d3-interpolate](https://github.com/d3/d3-interpolate) to animate the "randomize", "square" and "triangle" buttons & adding random jitter to fix the Voronoi cells.` | |
| )}) | |
| }, | |
| { | |
| inputs: ["md"], | |
| value: (function(md){return( | |
| md`## Appendix` | |
| )}) | |
| }, | |
| { | |
| name: "height", | |
| value: (function(){return( | |
| 720 | |
| )}) | |
| }, | |
| { | |
| name: "reduceBasis", | |
| value: (function(){return( | |
| function reduceBasis(b1,b2) { | |
| // dot product | |
| function dp(u,v) { | |
| return u[0]*v[0] + u[1]*v[1]; | |
| } | |
| let B1 = dp(b1,b1); | |
| let mu = Math.round(dp(b1,b2)/B1); | |
| b2[0] -= mu * b1[0]; | |
| b2[1] -= mu * b1[1]; | |
| let B2 = dp(b2,b2); | |
| while (B2 < B1) { | |
| [b1,b2] = [b2,b1]; | |
| B1 = B2; | |
| mu = Math.round(dp(b1,b2)/B1); | |
| b2[0] -= mu * b1[0]; | |
| b2[1] -= mu * b1[1]; | |
| B2 = dp(b2,b2); | |
| } | |
| return [b1,b2]; | |
| } | |
| )}) | |
| }, | |
| { | |
| name: "getParticles", | |
| value: (function(){return( | |
| function getParticles(m,n, {ax, ay, bx, by}) { | |
| const particles = []; | |
| for (let j = -m; j <= m; ++j) { | |
| const xj = j * ax; | |
| const yj = - j * ay; | |
| for (let i = -n; i <= n; ++i) { | |
| const p = [xj + i*bx + (1e-6*Math.random()), yj-i*by]; // jitter | |
| p.i = i; | |
| p.j = j; | |
| particles.push(p); | |
| } | |
| } | |
| return particles; | |
| } | |
| )}) | |
| }, | |
| { | |
| name: "renderVoronoi", | |
| inputs: ["d3","width","height"], | |
| value: (function(d3,width,height){return( | |
| function renderVoronoi(context, {particles}, {ax, ay, bx, by}, extra=1) { | |
| const w = extra*Math.max(Math.abs(ax), Math.abs(bx)); | |
| const h = extra*Math.max(Math.abs(ay), Math.abs(by)); | |
| const delaunay = new d3.Delaunay.from(particles.filter( | |
| d=> d[0] >-width/2-w && d[0] < width/2+w && | |
| d[1] >-height/2-h && d[1] < height/2+h)); | |
| const voronoi = delaunay.voronoi([-width/2, -height/2, width/2, height/2]); | |
| context.save(); | |
| context.translate(width / 2, height / 2); | |
| context.strokeStyle = 'rgba(0,128,128,1)' | |
| context.lineWidth = '2'; | |
| context.beginPath(); | |
| voronoi.render(context); | |
| context.stroke(); | |
| context.restore(); | |
| return voronoi; | |
| } | |
| )}) | |
| }, | |
| { | |
| name: "renderLattice", | |
| inputs: ["width","height"], | |
| value: (function(width,height){return( | |
| function renderLattice(context, {particles}, style=null) { | |
| context.save(); | |
| const w = width; | |
| const h = height; | |
| context.translate(w / 2, h / 2); | |
| const pp = particles.filter(([x,y]) => x+3 > -w/2 && x-3 < w/2 && y+3 > -h/2 && y-3 < h/2); | |
| for (const p of pp) { | |
| context.beginPath(); | |
| context.arc(p[0], p[1], 3, 0, 2 * Math.PI); | |
| context.fillStyle = style || | |
| "rgba(0,150,0,1)"; | |
| context.fill(); | |
| } | |
| context.restore(); | |
| } | |
| )}) | |
| }, | |
| { | |
| name: "renderBasis", | |
| inputs: ["width","height"], | |
| value: (function(width,height){return( | |
| function renderBasis(context, {ax, ay, bx, by}, clicked=null) { | |
| // const na = Math.sqrt(ax*ax+ay*ay)/8; | |
| // const nb = Math.sqrt(bx*bx+by*by)/8; | |
| context.save(); | |
| context.translate(width / 2, height / 2); | |
| // draw parallelogram | |
| context.beginPath(); | |
| context.moveTo(0,0); | |
| context.lineTo(ax,-ay); | |
| context.lineTo(ax+bx,-ay-by); | |
| context.lineTo(bx,-by); | |
| context.lineTo(0,0); | |
| context.lineWidth = '3'; | |
| context.strokeStyle = 'rgba(255,0,255,1)'; | |
| context.stroke(); | |
| context.lineWidth = '2'; | |
| // a | |
| context.beginPath(); | |
| context.arc(ax, -ay, clicked === 'a' ? 11 : 8, 0, 2 * Math.PI); | |
| context.fillStyle = 'rgba(128,255,128,1)'; | |
| context.fill(); | |
| if (clicked === 'a') | |
| context.stroke(); | |
| context.beginPath(); | |
| context.arc(ax, -ay, 3, 0, 2 * Math.PI); | |
| context.fillStyle = 'rgba(0,150,0,1)'; | |
| context.fill(); | |
| // b | |
| context.beginPath(); | |
| context.arc(bx, -by, clicked === 'b' ? 11 : 8, 0, 2 * Math.PI); | |
| context.fillStyle = 'rgba(128,128,255,1)'; | |
| context.fill(); | |
| if (clicked === 'b') | |
| context.stroke(); | |
| context.beginPath(); | |
| context.arc(bx, -by, 3, 0, 2 * Math.PI); | |
| context.fillStyle = 'rgba(0,150,0,1)'; | |
| context.fill(); | |
| // a+b | |
| context.beginPath(); | |
| context.arc(ax+bx, -ay-by, 5, 0, 2 * Math.PI); | |
| context.fillStyle = 'rgba(255,128,128,1)'; | |
| context.fill(); | |
| context.beginPath(); | |
| context.arc(ax+bx, -ay-by, 3, 0, 2 * Math.PI); | |
| context.fillStyle = 'rgba(0,150,0,1)'; | |
| context.fill(); | |
| // origin | |
| context.beginPath(); | |
| context.arc(0, 0, 5, 0, 2 * Math.PI); | |
| context.fillStyle = 'rgba(255,0,0,1)'; | |
| context.fill(); | |
| context.beginPath(); | |
| context.arc(0, 0, 3, 0, 2 * Math.PI); | |
| context.fillStyle = 'rgba(0,150,0,1)'; | |
| context.fill(); | |
| context.restore(); | |
| } | |
| )}) | |
| }, | |
| { | |
| name: "renderTextLattice", | |
| inputs: ["width","height"], | |
| value: (function(width,height){return( | |
| function renderTextLattice(context, {particles}, {shift,text,textFunc,font,fontSize,fillStyle}) { | |
| context.save(); | |
| const w = width; | |
| const h = height; | |
| context.translate(w / 2, h / 2); | |
| context.font = font || `${fontSize || 25}px serif`; | |
| context.fillStyle = fillStyle || 'white'; | |
| shift = shift || ((fontSize || 25)/ 2); | |
| const pp = particles.filter(([x,y]) => x+shift > -w/2 && x-shift < w/2 && y+shift > -h/2 && y-shift < h/2); | |
| for (const p of pp) { | |
| context.fillText(text || textFunc(p), p[0]-shift, p[1]+shift); | |
| } | |
| context.restore(); | |
| } | |
| )}) | |
| }, | |
| { | |
| name: "lilDot", | |
| value: (function(){return( | |
| function lilDot(color, fill=true) { | |
| return `<span style="display:inline-flex;align-items:center;vertical-align:middle;"><svg width="25" height="25" version="1.1" xmlns="http://www.w3.org/2000/svg"> | |
| <circle cx="12.5" cy="12.5" r="8" stroke="${color}" fill="${fill ? color : 'none'}" stroke-width="${fill ? 0 : 2}" /> | |
| </svg></span>` | |
| } | |
| )}) | |
| }, | |
| { | |
| name: "d3", | |
| inputs: ["require"], | |
| value: (function(require){return( | |
| require("d3@5", "d3-delaunay@4") | |
| )}) | |
| }, | |
| { | |
| from: "@mbostock/form-input", | |
| name: "form", | |
| remote: "form" | |
| } | |
| ] | |
| }; | |
| const m1 = { | |
| id: "@mbostock/form-input", | |
| variables: [ | |
| { | |
| name: "form", | |
| inputs: ["formValue"], | |
| value: (function(formValue){return( | |
| function form(form) { | |
| form.addEventListener("change", () => form.dispatchEvent(new CustomEvent("input"))); | |
| form.addEventListener("input", () => form.value = formValue(form)); | |
| form.value = formValue(form); | |
| return form; | |
| } | |
| )}) | |
| }, | |
| { | |
| name: "formValue", | |
| value: (function(){return( | |
| function formValue(form) { | |
| const object = {}; | |
| for (const input of form.elements) { | |
| if (input.disabled) continue; | |
| let value = input.value; | |
| switch (input.type) { | |
| case "range": | |
| case "number": { | |
| value = input.valueAsNumber; | |
| break; | |
| } | |
| case "date": { | |
| value = input.valueAsDate; | |
| break; | |
| } | |
| case "radio": { | |
| if (!input.checked) continue; | |
| break; | |
| } | |
| case "checkbox": { | |
| if (input.checked) value = true; | |
| else if (input.name in object) continue; | |
| else value = false; | |
| break; | |
| } | |
| case "file": { | |
| value = input.multiple ? input.files : input.files[0]; | |
| break; | |
| } | |
| } | |
| object[input.name] = value; | |
| } | |
| return object; | |
| } | |
| )}) | |
| } | |
| ] | |
| }; | |
| const notebook = { | |
| id: "0d0d4e55f05ea8aa@212", | |
| modules: [m0,m1] | |
| }; | |
| export default notebook; |