Published
Edited
May 24, 2021
md`# tally`
values = ({
max64: Math.pow(2, 64),
max32: Math.pow(2, 32),
max16: Math.pow(2, 16),
max8: Math.pow(2, 8),
})
MAX_VALUES = values
toHexString = bytes =>
bytes.reduce((str, byte) => byte.toString(16).padStart(2, '0')+str, '')
fromHexStr = hexString =>
new Uint8Array(hexString.match(/.{1,2}/g).map(byte => parseInt(byte, 16)));
values.max32
l = new Uint8Array(32).buffer
l instanceof ArrayBuffer
function significantLength(value) {
const len = value.length;
for (let i = len - 1; i >= 0; i--) {
if (value[i] !== 0) return i + 1;
}
return 0;
}
class tally {
constructor(value, bytes) {
if (value instanceof tally) {
this.buf = value.buf
this.a32 = new Uint32Array(this.buf);
this.a16 = new Uint16Array(this.buf);
this.a8 = new Uint8Array(this.buf);
} else {
if (value.buffer instanceof ArrayBuffer) {
// logger.log(value.buffer,"Arr")
this.buf = value.buffer
this.a32 = new Uint32Array(this.buf);
this.a16 = new Uint16Array(this.buf);
this.a8 = new Uint8Array(this.buf);
} else {
this.buf = new ArrayBuffer(bytes);
this.a32 = new Uint32Array(this.buf);
this.a16 = new Uint16Array(this.buf);
this.a8 = new Uint8Array(this.buf);
let c = value
for (let i = 0 ; i<bytes ; i++) {
this.a32[i] = c % values.max32
c = Math.floor(c / values.max32)
}
}
}
}
static add(a, b) {
let l = Math.max(a.a32.byteLength, b.a32.byteLength)
let c = new tally(0, l+4 )
for (let i=0;i<Math.ceil(l/4);i++) {
let t = a.a32[i] + b.a32[i]
if (t > (values.max32 - 1)){
c.a32[i+1] = 1
}
c.a32[i] = c.a32[i] + t;
}
if (c.a32[l]) {
logger.log("overflow")
return c;
}
return new tally(c.a32.slice(0, c.a32.length-1), l);
}
static mul(a, b) {
let l = a.a32.byteLength + b.a32.byteLength
let c = new tally(0, l)
let carry,temp
for (let i=0; i<a.a16.length; i++) {
carry = 0
for (let j=0; j<b.a16.length; j++) {
temp = c.a16[i + j] + carry + a.a16[i] * b.a16[j]
carry = Math.floor(temp / MAX_VALUES.max16)
c.a16[i + j] = temp % MAX_VALUES.max16
// c[i + j] = c[i + j] mod base
}
c.a16[i + a.a16.length] = carry
}
if (carry)logger.log("overflow")
return new tally(c.a16.slice(0, a.a16.length));
}
static sub(a,b){
let l = Math.max(a.a32.byteLength, b.a32.byteLength)
let c = new tally(0, l)
for (let i=0;i<Math.ceil(l/4);i++) {
let u = a.a32[i]<b.a32[i]
let t = a.a32[i]
if (u) {
a = tally._carry(a,i)
t = t + MAX_VALUES.max32
}
c.a32[i] = t - b.a32[i]
}
return c;
}
static _carry(a,i){
if (i === a.a32.length) return a
a.a32[i+1] = a.a32[i+1] - 1
if (a.a32[i+1] === MAX_VALUES.max32-1) {
return tally._carry(a,i+1)
}
return a
}
// static sub16(a,b){ // maybe NOT needed
// let c = new Uint16Array(16)
// //let carry = new Uint16Array(1);
// for (let i=0;i<c.length;i++) {
// let u = a[i]<b[i]
// let t = a[i]
// if (u) {
// a = this._carry16(a,i)
// t = t + Math.pow(2, 16)
// }
// c[i] = a[i]-b[i]
// }
// return c;
// }
// static _carry16(a,i){
// if (i+1 === a.length) return a
// a[i+1] = a[i+1] - 1
// if (a[i+1] === 0xffff) {
// return this._carry(a,i+1)
// }
// return a
// }
static _div(a, b){
// let cat = new tally(0, a.a32.byteLength)
// let set = new tally(0, a.a32.byteLength)
let cat = new Uint16Array(16);
let set = new Uint16Array(16);
if (tally._iszero(b) || tally._iszero(a)) {
// return [cat, set];
return [new tally(0, 32), new tally(0, 32)]
}
if (tally._gt(b,a,b.a16.length-1)) {
// return [cat, new tally(a.a16.slice(0), a.a16.byteLength)];
return [new tally(0, 32), new tally(a.a16.slice(0), a.a16.byteLength)];
}
function shr (n) {
const len = 14;
for (let i = len; i >= 0; i--) {
n[i + 1] = n[i];
}
n[0] = 0;
return n;
}
const slen = significantLength(b.a16);
const slena = significantLength(a.a16);
let pos = slena - slen;
for (let i = 0; i < slen; i++) {
set[i] = a.a16[i + pos];
}
const [n, c] = tally._findDiv(set, b);
cat[0] = n;
set = c.a16;
let reps = 0;
while (pos > 0) {
reps ++;
if (tally._gt(b, new tally(set), b.a16.length - 1)) {
set = shr(set);
pos --;
set[0] = a.a16[pos];
}
const [n, c] = tally._findDiv(set, b);
cat = shr(cat);
cat[0] = n;
set = c.a16;
if (reps > 40) return [new tally(cat), new tally(set)]
}
return [new tally(cat), new tally(set)]
}
// n1 > n2
// n1.length <= n2.length + 1
static _findDiv(n1, t2) {
const n2 = t2.a16;
const t1 = new tally(n1);
const len1 = significantLength(n1);
const len2 = significantLength(n2);
let catMax;
if (len1 < len2) throw new Error('_findDiv n1 < n2');
if (len2 === len1) catMax = Math.floor(n1[len1 - 1] / n2[len2-1]);
else {
const divident = n1[len1 - 1] * MAX_VALUES.max16 + n1[len1 - 2];
const cat = Math.floor(divident / n2[len2-1]);
catMax = cat < MAX_VALUES.max16 ? cat : MAX_VALUES.max16 - 1;
}
const prod1 = tally.mul(t2, new tally(catMax, 32));
if (tally._eq(prod1, t1)) return [catMax, new tally(0, 32)];
if (tally._lt(prod1, t1, prod1.a16.length - 1)) return [catMax, tally.sub(t1, prod1)];
catMax -= 1;
return [catMax, tally.sub(t1, tally.mul(t2, new tally(catMax, 32)))];
}
static mod(a, b){
let c = tally._div(a,b)
//p(q,r)
return c[1];
}
static div(a, b){
let c = tally._div2(a,b)
//p(q,r)
return c;
}
static addmod(a, b, c){
let d = tally.add(a, b)
let e = tally._div(d,c)
return e[1];
}
static mulmod(a, b, c){
let d = tally.mul(a,b)
let e = tally._div(d,c)
return e[1];
}
static lt(a, b) {
let c = new tally(0, a.a32.byteLength)
c.a8[0] = tally._lt(a,b,a.a32.length-1)? 1:0
return c;
}
static _lt(a, b, i) {
//logger.log(a,b,i)
if (i === -1) return false
if (b.a32[i] < a.a32[i]) return false
if (b.a32[i] == a.a32[i]) return (true && tally._lt(a, b, i-1))
return true;
}
static gt(a, b){
let c = new tally(0, a.a32.byteLength)
c.a8[0] = tally._gt(a,b,a.a32.length-1)? 1:0
return c
}
static _gt(a, b, i){
// logger.log("abi ",a[i],b[i],i)
if (i === -1) return false
if (b.a32[i] > a.a32[i]) return false
if (b.a32[i] == a.a32[i]) return (true && tally._gt(a, b, i-1))
return true;
}
static eq(a, b){
let c = new tally(0, a.a32.byteLength)
c.a8[0] = tally._eq(a, b)? 1 : 0
//p(t,a,b,c)
return c;
}
static _eq(a,b){
let t = true
let l = Math.max(a.a32.length, b.a32.length)
for (let i=0;i<l;i++) {
t = t && b.a32[i] === a.a32[i]
}
return t
}
static iszero(a){
let c = new tally(0, a.a32.byteLength)
c.a8[0] = tally._iszero(a)
return c;
}
static _iszero(a){
let t = true
for (let i=0; i < a.a32.length; i++) {
t = t && a.a32[i] === 0
}
return t
}
static _isone(a){ // ---
let t = true
for (let i=1; i < a.a32.length; i++) {
t = t && a.a32[i] === 0
}
return a.a32[0] ==1 ? t: false;
}
static and(a, b){
let f = (a, b) => a & b
return tally._bit2(a, b, f)
}
static _bit2(a, b, fx){
let c = new tally(0, a.a32.byteLength)
for (let i=0;i<c.a32.length;i++) {
c.a32[i] = fx(a.a32[i], b.a32[i])
}
return c;
}
static or(a, b){
let f = (a, b) => a | b
return tally._bit2(a, b, f)
}
static xor(a, b){
let f = (a, b) => a ^ b
return tally._bit2(a, b, f)
}
static not(a){
let b = new tally(0, a.a32.byteLength)
for (let i=0;i<a.a32.length;i++) {
b.a32[i] = ~ a.a32[i]
}
return b
}
static shl(a, b){
let c = new tally(0, a.a32.byteLength + 4)
for (let i=0; i<a.a32.length; i++) {
let t = a.a32[i] * Math.pow(2,b.a8[0])
c.a32[i] = t % MAX_VALUES.max32
c.a32[i+1] = c.a32[i+1] + t/MAX_VALUES.max32;
}
return c
}
static shr(a, b){
let c = new tally(0, a.a32.byteLength + 4)
for (let i=a.a32.length; i>-1; i--) {
let t = Math.floor(a.a32[i-1] / Math.pow(2,b.a8[0]))
c.a32[i] = t
let t2 = a.a32[i-1] % Math.pow(2,b.a8[0])
c.a32[i-1] = c.a32[i-1] + t2*MAX_VALUES.max32/Math.pow(2,b.a8[0]);
}
return new tally(c.a32.slice(1), a.a32.byteLength);
}
static empty(length = 32) {
return new tally(0, length);
}
static neg(a) {
return tally.sub(tally.empty(), a);
}
static isNeg(a) { // ---
return tally._isNeg(a)? new tally(1, 32) : new tally(0, 32);
}
static _isNeg(a) { // ---
return (a.a32[a.a32.length - 1] > 0xefffffff);
}
static abs(a) { // ---
return tally._isNeg(a)? tally.neg(a) : a;
}
toString (encoding, size) {
// encoding = encoding || 16;
// size = size || this.a8.byteLength;
// const arr = this.a8.slice(0, size).reverse();
// return u8ToString(arr, 'base' + encoding);
return this.a8;
}
clone(){
let f = this.a8.slice(0)
return new tally(f)
}
static _div2(a2, b2){
let a = a2
let b = b2
if (tally._iszero(b) || tally._iszero(a) ) {
return [new tally(0, 32), new tally(a.a16.slice(0), a.a16.byteLength)]
}
let q = new tally(0, 32);
let r = new tally(0, 32);
let m = new tally(0, 32);
let bb = 0 , lb, la
let qq
for (let y = b.a16.length-1; y>-1; y--) {
bb = b.a16[y]? b.a16[y] : bb
lb = (!bb)? b.a16.length-y: lb
}
for (let i = (a.a16.length-1); i>-1; i--) {
//if (!m.a16[i+1]) {
for (let j = (a.a16.length-1); j>0; j--) {
m.a16[j] = m.a16[j-1]
}
m.a16[0]= a.a16[i]
//}
console.log("bb",bb, i, m.a16[0], m.a16[i],m.a16[i+1])
if (m.a16[0]>bb || m.a16[1]>0) {
let q2 = new tally(0,32)
let t1 = 0, t2 = 0
if (i < a.a16.length -1) t1 = m.a16[1]
let t = t1*values.max16 + m.a16[0]
q2.a16[i] = Math.floor(t / bb)
let n = tally.mul(b ,q2)
let k = tally._gt(n,a,a.a32.length-1)
if (k) {
q2.a16[i] = q2.a16[i] - 1
n = tally.mul(b ,q2)
}
la = la? la : i
//a = tally.sub(a, n)
m.a16[1] = 0
m.a16[0] = t - bb*q2.a16[i]
let a1 = tally.sub(a, n)
a = a1
q.a16[i-(15-la+lb)] = q2.a16[i]
}
//r.a16[0] = m.a16[0]
//logger.log("a,a1,i!!?!!",i,a.a16.toString(),a1.a16.toString())
}
// for (let j = (q.a16.length-1); j>0; j--) {
// q.a16[la - lb -j] = q.a16[j]
// }
console.log(la,lb,a, b, q);
return [q, a];
}
static rand(l) { // ---
let arr8 = new Uint8Array(l)
for (let i=0; i<l; i++) {
arr8[i] = Math.floor(Math.random()*255)
}
return new tally(arr8);
}
static gcd(a, b) { // ---
//logger.log("gcd ",a, b,tally._gt(a, b, a.a32.length-1))
mutable count_loops ++;
if (tally._iszero(b)) return a;
if (tally._iszero(a)) return b;
if (tally._gt(a, b, a.a32.length-1)) {
return tally.gcd(tally.sub(a, b), b);
} else {
return tally.gcd(a, tally.sub(b, a));
}
}
static lcm(a, b) { // ---
return tally.div(tally.mul(a, b), tally.gcd(a, b))
}
static isEven(a) { // ---
return (a.a8[0] & 1) === 0;
};
static isOdd(a) { // ---
return (a.a8[0] & 1) === 1;
};
}
class flex { // lax
static value(name){
const values = {
pi: new flex(new tally(new Uint8Array([250,212,212,212]),new tally(new Uint8Array([250])))),
va: new flex(new tally(new Uint8Array([11,0,0,0,212,212]),new tally(new Uint8Array([251])))),
}
return values[name]
}
constructor(mantissa, exponent){
if (mantissa instanceof tally && exponent instanceof tally) {
this.exponent = exponent;
this.mantissa = mantissa;
} else {
return null
}
}
static shiftr(f1, n) {
let f2 = new flex(f1.mantissa, tally.sub(f1.exponent, new tally(n,4)))
return f2;
}
static add(f1, f2) {
let c, d,sum
if (tally._gt(f2.exponent, f1.exponent, 0)) {
c = f1
d = f2
} else {
c = f2
d = f1
}
console.log(c,d)
console.log(c,d,sum)
d = flex.shiftr(d, tally.sub(c.exponent,d.exponent))
console.log(c,d,sum)
c.mantissa = tally.add(c.mantissa, d.mantissa) //, new tally(2,4)) //[0]
console.log("aaa",c,d)
sum = new flex(c.mantissa, tally.add(f1.exponent, new tally(1,4)))
return sum;
// shift m(d) right (e(c) − e(d)) places // arithmetic right shift
// m(c) = m(c) + m(d); //twos-complement addition
// if ( sgn(m(a)) = sgn(m(b)) ) {
// if ( sgn(m(c)) ! = sgn(m(a)) ) { // signed overflow
// e(sum) = e(a) + 1;
// m(sum) = m(c)/2;
// // done
// }
// }
// // possible subtractive cancellation
// s = number of leading sign bits in 2 · m(c)
// e(sum) = e(a) − s;
// m(sum) = m(c) << s;
}
static mul(f1, f2) {
//signed multiplication of mantissas
let mul = new flex(tally.mul(f1.mantissa, f2.mantissa), tally.add(f1.exponent, f2.exponent))
// m(product) = m(a) · m(b); // keep high 256 bits of unsigned product
// if (m(a) < 0)
// m(product) = m(product) − m(b);
// if (m(b) < 0)
// m(product) = m(product) − m(a);
// s = number of leading sign bits in 2 · m(product)
// e(product) = e(a) + e(b) − s;
// m(product) = m(product) << s; // truncate result to 224 bits
return mul;
}
static div(f1, f2) {
let div = new flex(tally.div(f1.mantissa, f2.mantissa), tally.sub(f1.exponent, f2.exponent))
return div;
}
static mod(f1, f2) {
let mod = new flex(tally.mod(f1.mantissa, f2.mantissa), tally.sub(f1.exponent, f2.exponent))
return mod;
}
}
new tally(1,4)
h1 = new flex(new tally(new Uint32Array([240,34,56,223,55,22,33]),28), new tally(new Uint32Array([11]),4))
h2 = new flex(new tally(new Uint32Array([240,34,56,223,55,22,33]),28), new tally(new Uint32Array([14]),4))
h3 = flex.add(h1, h2)
{
let h12 = new flex(new tally(new Uint32Array([240,34,56,223,55,22,33]),28), new tally(new Uint32Array([11]),4))
let h22 = new flex(new tally(new Uint32Array([240,34,56,223,55,22,33]),28), new tally(new Uint32Array([14]),4))
return flex.add(h12, h22)
}
h4 = flex.mul(h1, h2)
quasi.asTally(quasi.value("va"))
quasi.value("va")
mutable count_loops = 0
function randTally(l){
let arr8 = new Uint8Array(l)
for (let i=0; i<l; i++) {
arr8[i] = Math.floor(Math.random()*255)
}
return new tally(arr8);
}
c1 = tally.rand(32)
c2 = tally.rand(32)
//c3 = tally.gcd(c1, c2)
c4 = tally.lcm(c1, c2)
d3= tally.div(c1, c2)
tally.add(tally.mul(d3[0], c2), d3[1]) // div proof
tally._gt(c1,c2,32)
logger = console
require('https://bundle.run/bn.js@5.2.0')
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
