Additional info related to prior post

From my examination of $isbit, I'm wondering if - either the same thing causing $isbit to be slow could be the same thing causing $powmod to slow down, or else this might be a way to optimize $powmod, depending on how much time is spent checking the Nth bit of the exponent compared to doing the multiplies and squares. Below is a solution that makes $isbit faster than it currently is, though it might not be the optimum long-term solution.

--

I know you had mentioned that a past GPF in powmod had been caused by ever-increasing length of a fraction, so maybe the 40% chance in $powmod speed for this beta is related to getting the Nth bit of the exponent a different way. And, this might also be related to the reason why $isbit is slow.

The alias below creates a random number having bit length of N, and then uses 6 methods to rebuild it bit-by-bit.

#1 the new .bf mode capability for $isbit to get the value of each bit position

#2 a kludge that uses $base() to translate the number into a long base2 text string, then uses $mid to see what's the Nth bit from the right.

#3 Same kludge as #2 except it cheats by doing something $isbit can't do, which is assuming the input number is constant, so it can pre-calculate the $base result 1 time to avoid N-1 calls to $base, using $mid against the already existing string.

#4 Same cheat as #3, except using a &binvar instead of a text string.

#5 Another cheat taking advantage of the input number being constant, making a copy of the input number then calculates the Nth bit similar to how $powmod parses the exponent

#6 While this is slower than #4, it is not a cheat relying on the input number being constant, and is significantly faster than #1 doing the same thing using $isbit

Benchmark times compared to #1's usage of $isbit seem to be...

#2 kludge is fairly consistent around 200% the time as #1, though intuitively I would've expected the multiplier distance to be much greater.

#3 vs #2 shows that the bottleneck for #2 is almost entirely the repeated calls to $base, and without the repeated calls to $base the time is less than 2% that of $isbit.

#4 vs #3 shows that #4 has a significant percent speed above #3 by using a &binvar instead of a %text.string.

#5 Because this imitates $bf_modpow, and is slower than #4 imitating $bf_modpow2, that might indicate a significant speedup for the portion of $powmod's time spent manipulating the exponent when it's not busy squaring and multiplying

#6 This one doesn't use the #3-5 cheat of a constant input number, so is relevant to the speed of $isbit.

While the #3 and #4 cheats are not the kind of thing that can help $isbit speed up, they're precisely the kind of thing that might help $powmod, if $powmod is currently doing math similar to #5.

$isbit:

I'm not saying that #6 is the most efficient way to calculate the Nth bit of a number, but it benchmarks at like 2% of the time that $isbit takes in #1, and Talon can probably suggest an even faster way to calculate it.

--

So below is a scripted bf_modpow2 update to my original alias, where in the original I was repeatedly dividing the exponent by 2 and calculating the modulo-2 result, even though I was interested only in the value of the Nth bit, and I knew there would be a performance penalty from trying to access a text string, but hadn't considered using a &binvar yet. Since this style of alias doesn't care about the full value of the exponent at each intermediate stage, the libraries would do the floor-divide-by-2 as shifting all the bits 1 position to the right. And the modulo-2 is then done instead by just checking the lowest bit. Or, combining both the shift and peek at the lowest bit as a getbit(). But I gather that's not compatible with how MAPM stores data.

So if a profiler determines that $powmod is spending a lot of time diving the N-bit exponent N times or otherwise checking the Nth bit, it might be faster to use the style#4 method to pre-calculate values of all bit positions, hopefully something more efficient than a call to $base(). And then during each loop could check array[pointer] rather than doing big-math. The cost/benefit timing from changing a script is almost surely different for compiled code.

This modified bf_modpow2 is the same as the original bf_modpow except for 2 things. It has updated handling to discard fractions and handle negatives. But the main difference is how it checks for the bit values of the exponent. Where B is the number of bits in the exponent:

old:
a.
b.
c.
d. calculate (exponent % 2) to see if result == 1, repeated B times
e. calculate (exponent // 2) then set exponent to new value, repeated B times
f. check if potentially huge bigfloat exponent is now zero, repeated B times

new:
a. use $base to translate exponent to base2 text string, done 1 time
b. create &temp binvar containing that text string, done 1 time
c. create %bit.pos pointing to the least-value bit position, done 1 time
d. check if the Nth lowest byte of &temp is '1', repeated B times
e. decrease %bit.pos pointer by 1, repeated B times
f. check if short integer is now zero, repeated B times

For bf_modpow2 I am seeing much wider fluctuations in completion time than I saw for bf_modpow, but the best times at 2048 and 4096 in the various betas have a very minor gain in speed compared to bf_modpow. Intuitively I would expect there's more of a performance gain by checking the value of a &binvar's byte instead of perform a modulo-2 calculation against a huge bigfloat number, and then repeatedly floor dividing a bigfloat number by 2, which remains a bigfloat until the last 53 loops - than the performance hit for the time needed to translate a very large integer from base10 to base2 and then stuff it into a &binvar.

So if the slowness for $isbit is the same thing that caused $powmod to be 40% slower in 3337 than 2385, perhaps a single pre-calculation of the exponent might enable $powmod to return to its former speed, or to possibly even have the same speed relationship in 1743 where $powmod took 40% of the bf_modpow time instead of the current 95-98%.

And, the style#6 can help the speed of $isbit be 50x faster, unless there's a better method than I created off-the-cuff.

* *

Updated bf_modpow2 has interchangeable syntax with $powmod, so both custom aliases and $powmod can be used interchangably as the identifier in the earlier posts's //command.

The mapm_isbit alias defaults to bit length 512, but can be changed by $1 being as high as $maxlenl. It creates a random number of the specified bit length, then creates from it a similar exponent then shows the time required to perform the slow $powmod calculation against a number is faster than the time needed by $isbit to access all the bits. It then shows the time needed to re-create the random number using each of the 6 methods described above, of which only style#2 is slower. It verifies the result matches the original random number and resets /fupdate back to original, having changed it to avoid fupdate=0 affecting the timing.

Code
alias bf_modpow2 {
  var %base.bf $gettok($1,1,46) , %exponent.bf $gettok($2,1,46) , %modulus.bf $gettok($3,1,46)
  var %answer.bf 1

  if (!$regex(%base.bf %exponent.bf %modulus.bf,^-?\d+ -?\d+ -?\d+$)) return $calc(0/0)
  ; (base=any integer, exp=any integer, mod=any integer) result always [0,modulus-1]

  ; modulus = abs(modulus)
  if (-* iswm %modulus.bf) var %modulus.bf $regsubex(foo,$v2,^(-*)(.*)$,\2)
  ; (base=anything, exp=anything, mod >= 0)

  ; (any % 1 = 0); (any % 0 = divide by zero)
  ; if (%modulus.bf == 0) return $calc(0/0)
  if (%modulus.bf < 2) return 0
  ; (base=anything, exp=anything, mod >= 2)

  ; if (base < 0) base = modulus - (abs(base) % modulus)
  if (-* iswm %base.bf) var -s %base.bf $calc( %modulus.bf - $regsubex(foo,$v2,^(-*)(.*)$,\2) )
  ; aka -N % mod -> [0,mod-1] -> (-N+mod) % mod
  ; (base >= 0, exp=anything, mod >= 2)

  if (%exponent.bf < 2) {
    ; any^0 = 1
    if (%exponent.bf == 0) return 1
    ; base is positive, so for base^1 return [0,mod-1] as (base % modulus)
    if (%exponent.bf == 1) return $calc( %base.bf % %modulus.bf)

    ; remaining case here is (exp < 0)
    if (%exponent.bf  < 0) {
      ; powmod(+base,-exp, +mod) -> powmod( mod_inverse(+base,modulus) , +exp, +mod)
      ; exp = abs(exp)
      var %exponent.bf $regsubex(foo,%exponent.bf,^(-*)(.*)$,\2)
      ; base = inverse(+base,modulus)
      var %base.bf $ModInv( %base.bf , %modulus.bf )
      ; 6^-2 mod 15 -> 6^(-1*2) mod 15  -> 6^(-1)^2 mod 15 -> (1/6)^2 mod 15 -> modinv(6,15)^2 mod 15 -> 3^2 mod 15 = 9
      ; if (%base.bf == -1) return -1
      ; -1 when there is no inverse ie (5,-anything,15)
    }
  }
  ; (base >= 0, exp >= 2, mod >= 2)

  if (%base.bf < 2) {
    ; 0^any = 0; 1^any = 1; i.e. return val matches base
    return %base.bf
  }
  ; (base >= 2, exp >= 2, mod >= 2)

  ;  echo -s $scriptline base: %base.bf exp: %exponent.bf modulus: %modulus.bf

  ; intentional skip of leading zero bits, requires code above to prevent seeing exponent <= 0
  bset -tc &temp 1 $base(%exponent.bf,10,2)
  ;breplace &temp 48 0
  var %bit.pos $bvar(&temp,0)
  ;echo -a $bvar(&temp,0) / $bvar(&temp,1-)
  ;var %binary_exponent.bf $base(%exponent.bf,10,2) , %bit.pos $len(%binary_exponent.bf)
  ;    if ($mid(%binary_exponent.bf,%bit.pos,1)) { var %answer.bf $calc( (%answer.bf * %base.bf) % %modulus.bf ) }
  while (%bit.pos > 0) {
    if ($bvar(&temp,%bit.pos) == 49) { var %answer.bf $calc( (%answer.bf * %base.bf) % %modulus.bf ) }
    ; this next calc multiplies base*base because base^2 returns the wrong result in .bf mode
    var %base.bf $calc( (%base.bf * %base.bf) % %modulus.bf ) , %bit.pos %bit.pos - 1
  }
  return %answer.bf
  :syntax
  echo -sc info *$bf_modpow(base,exponent,modulus)
  halt
}
[code]



[code]
alias mapm_bitwise_style1 { if ($isbit($1,$2)) return 1 | return 0   }
alias mapm_bitwise_style2 { return $mid($base($1,10,2),- $+ $2,1)    }
alias mapm_bitwise_style3 { return $mid($hget(maroon,tmp),- $+ $2,1) }
alias mapm_bitwise_style4 { return $bvar($1,$2)                      }
alias mapm_bitwise_style5 { return $calc(($1 //(2^($2 -1))) % 2)     }

alias mapm_isbit {
  var -s %fupdate $fupdate
  fupdate 95
  var %bits $int($1)
  if ($1 !isnum 1- $maxlenl) { echo -ag $ $+ 1 not 1-10240 - using 512 bit number | var %bits 512 }
  echo -ag processing %bits bit number, warning this can be slow - press ctrl+break if needed
  var %num.bf $rand($calc(2^(%bits -1)),$calc(2^%bits))
  var %exp.bf $calc(%num.bf - 3) , %ticks $ticksqpc , %powmod $powmod(2,%exp.bf,%num.bf)
  echo -a powmod time: $calc($ticksqpc - %ticks)

  var %i 1, %build , %ticks $ticksqpc
  while (%i isnum 1- %bits) {
    var %b $mapm_bitwise_style1(%num.bf,%i) | var %build %b $+ %build
    inc %i
    if (*00 iswm %i) echo -a debug: i %i
  }
  var %stop $ticksqpc, %n2 $base(%build,2,10)
  echo -a diff: $calc(%num.bf - %n2) style#1 isbit time: $calc($ticksqpc - %ticks)

  var %i 1, %build , %ticks $ticksqpc
  while (%i isnum 1- %bits) {
    var %b $mapm_bitwise_style2(%num.bf,%i) , %build %b $+ %build
    inc %i
    if (*00 iswm %i) echo -a debug: i %i
  }
  var %stop $ticksqpc, %n2 $base(%build,2,10)
  echo -a diff: $calc(%num.bf - %n2) style#2 base(num,10,2) at each bit time: $calc(%stop - %ticks)

  var %i 1, %build , %ticks $ticksqpc | hadd -mu9999 maroon tmp $base(%num.bf,10,2)
  while (%i isnum 1- %bits) {
    var %b $mapm_bitwise_style3(%num.bf,%i) , %build %b $+ %build
    inc %i
    if (*00 iswm %i) echo -a debug: i %i
  }
  var %stop $ticksqpc, %n2 $base(%build,2,10)
  echo -a diff: $calc(%num.bf - %n2) style#3 base(num,10,2) 1 time then fetch from hashtable time: $calc(%stop - %ticks)

  var %build , %ticks $ticksqpc
  bset -tc &temp 1 $base(%num.bf,10,2) | breplace &temp 48 0 | breplace &temp 49 1
  var %i $bvar(&temp,0)
  while (%i) {
    var %b $mapm_bitwise_style4(&temp,%i) , %build %b $+ %build
    dec %i
    if (*00 iswm %i) echo -a debug: i %i
  }
  var %stop $ticksqpc, %n2 $base(%build,2,10)
  echo -a diff: $calc(%num.bf - %n2) style#4 base(num,10,2) 1 time then fetch from &binvar time: $calc(%stop - %ticks)

  var %i 1, %build , %ticks $ticksqpc
  var %temp.bf %num.bf
  while (%i isnum 1- %bits) {
    var %b 0 | if ($calc(%temp.bf % 2)) var %b 1 | var %build %b $+ %build
    var %temp.bf $calc(%temp.bf // 2)
    inc %i
    if (*00 iswm %i) echo -a debug: i %i
  }
  var %stop $ticksqpc, %n2 $base(%build,2,10)
  echo -a diff: $calc(%num.bf - %n2) style#5 at each bit bit=num%2 then num=num//2 time: $calc(%stop - %ticks)

  var %i 1, %build , %ticks $ticksqpc
  while (%i isnum 1- %bits) {
    var %b $mapm_bitwise_style5(%num.bf,%i) , %build %b $+ %build
    inc %i
    if (*00 iswm %i) echo -a debug: i %i
  }
  var %stop $ticksqpc, %n2 $base(%build,2,10)
  echo -a diff: $calc(%num.bf - %n2) style#6 at each bit calc(num//(2^(bitpos-1))) % 2)   time: $calc(%stop - %ticks)

  fupdate %fupdate
}