Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Decompose n into array of factor 'chunks' of n! #26

Closed
0joshuaolson1 opened this issue Feb 25, 2018 · 4 comments
Closed

Decompose n into array of factor 'chunks' of n! #26

0joshuaolson1 opened this issue Feb 25, 2018 · 4 comments

Comments

@0joshuaolson1
Copy link
Owner

0joshuaolson1 commented Feb 25, 2018 •
edited
Loading

Create an alternative ntop (and associated entropy estimator) that can easily pull from arrays (not like a) of 2^x, [21*23*25 /*< 2**53*/], etc.

Note to self: see if any (odd-number double) factorial identities in https://arxiv.org/abs/0906.1317 could help; or see:

Other identities?
@0joshuaolson1
Copy link
Owner Author

0joshuaolson1 commented Feb 25, 2018 •
edited
Loading

When writing the following, I found out that the 1.x readmes had the wrong 18! (so I finally published 2.x):

f=(n,a=[],b=-1)=>{
 if(n<=2)return[a,b+n] // [array of n!'s odd 'factors', (2^)x remainder]
 for(i=n%2?n--:n-1;i>1;i-=2)a.push(i)
 return F(n/=2,a,b+n)
}
a=f(18)
n=1<<a[1]
a[0].forEach(a=>n*=a)
console.log(n,a)

@0joshuaolson1 0joshuaolson1 mentioned this issue Feb 25, 2018
Open
@0joshuaolson1
Copy link
Owner Author

0joshuaolson1 commented Feb 26, 2018 •
edited
Loading

Shortcuts:

  • b is n - n's popcount of set (1) bits
  • a.length is n - ceil(lg n) - 1, but:

From now on, assume we instead split a into increasingly short (decreasingly long?) subarrays, one per 3[, 5...] run, so

  • a[i].length is floor((n - 2^i)/2^(i+1))
  • the i in a[i] to use for an n (and how much of b to use) is ntz(n) (consume a[i]*2^(ntz(n) b-bits) of entropy)
    • unless popcount(n) is 1 (n is a power of 2), then no a[i] (1 instead)
    • otherwise, the j in a[i][j] (assuming a[i][0] is 3) is floor((n - 2^i)/2^(i+1)) - 1 (but unnecessary with a cursor/finger optimization)
      • a[i][j] (entropy range) is j*2 + 3

popcount/Hamming weight and ntz/lsb helpers to sift through:

@0joshuaolson1
Copy link
Owner Author

0joshuaolson1 commented Feb 26, 2018 •
edited
Loading

I'm not yet sure which order has naturally better chunking:

  • reusable (3, 5, 7...)
  • adjacent (3, 5, 3, 7, 9, 5, 11, 3...)

The following ES7 shows that in both cases with a simple chunk search strategy and even with bignums, chunking near a power of 2 stays close above a power of 2 itself, and the following only shows the worst cases, not how often bad ones are encountered:

I=require('./node_modules/jsbn').BigInteger
z=(s,r)=>new I(s+'',r)
N=530 // to see an undiagnosed bug, make bigger like 5300; observe a[1].toString() trailing zeros
f=(i,a)=>{
 B=i=>{
  for(;i%2<1;)i/=2
  return z(i)
 }
 if(a){
  n=B(i)
  if(n.intValue()<2)n=B(++i)
 }
 else n=z(i)
 for(m=z(0);;n=n.multiply(a?B(++i):z(i+=2))){
  l=n.bitLength()
  if(l>N)return[j,m]
  M=n.multiply(z(2).pow(N-n.bitLength()))
  if(M.compareTo(m)>0){
   m=M
   j=i
  }
 }
}
r=A=>{
 p=z(2).pow(N)
 for(i=3;;i=2-A+a[0]){
  a=f(i,A)
  if(a[1].compareTo(p)<0){
   console.log(i,[a[0],(s=a[1].toString(2),z(s.substring(0,s.lastIndexOf('1')+1),2).toString()),a[1].toString()])
   p=a[1]
  }
 }
}
//r(0) // reusable order
//r(1) // adjacent order

Next to try:

  • combine chunks, noting that worst cases fall almost 4 times into next-power-of-2 entropy ranges but 2 best cases are not enough to fall twice
  • find a robust way to permute runs, like with easily found moduli coprime to run lengths, and use in a similar search strategy

@0joshuaolson1 0joshuaolson1 changed the title Decompose n into array of non-bignums Decompose n into array of factor 'chunks' of n! Feb 27, 2018
@0joshuaolson1 0joshuaolson1 mentioned this issue Mar 2, 2018
Closed
@0joshuaolson1
Copy link
Owner Author

I have too little confidence that this improves over actual numeric computing.

@0joshuaolson1 0joshuaolson1 mentioned this issue Mar 10, 2018
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@0joshuaolson1