Threaded Mode | Linear Mode

Joe Horn · (This post was last modified: 03-02-2015 07:06 AM by Joe Horn.)

EDIT: This discussion's original title was:
Request for "Multiplicative Order of Y (mod X)" program
... but my actual goal is the "decimal period of 1/X in base Y", which I wrongly thought was the same thing. Hence the confusion as the discussion progresses below...

Has anybody already written a Prime program to calculate the Number Theory value of "the multiplicative order of Y (mod X)"?

One application of this concept is found in repeating decimal numbers. For example, 1/13 = 0.076923076923... where "076923" repeats forever. Notice that the repeating section of 1/13 is 6 digits long. In Number Theory, they express this as "the multiplicative order of 10 (mod 13) = 6" with the 10 coming from the fact that decimal numbers (as the name implies) use base 10. "Multiplicative order" is often shortened to just "order".

Another example: In hexadecimal, 1/Dh (that's 1/13 in decimal) = 0.13B13B13B...h, where the three hex digits "13B" repeat forever. So the order of 16 (mod 13) = 3.

In Mathematica, it's implemented as MultiplicativeOrder[y,x].

Thanks in advance to anybody who has already programmed their Prime to find the order of Y (mod X). It shouldn't be too hard, since Prime has EULER, IDIVIS, and MODPOW built in.

Thomas Ritschel · 02-27-2015, 08:49 AM

Here is a simple non-CAS variant:

Code:

EXPORT MultiplicativeOrder(a,base)

BEGIN

  LOCAL k:=0;

  LOCAL res:=1;

  REPEAT

    res:=res*base;

    k:=k+1;

    res:=res MOD a;

  UNTIL res==1;

  RETURN(k);

END;

Gerald H · 02-27-2015, 09:35 AM

(02-27-2015 06:13 AM)Joe Horn Wrote: Has anybody already written a Prime program to calculate the Number Theory value of "the multiplicative order of Y (mod X)"?

One application of this concept is found in repeating decimal numbers. For example, 1/13 = 0.076923076923... where "076923" repeats forever. Notice that the repeating section of 1/13 is 6 digits long. In Number Theory, they express this as "the multiplicative order of 10 (mod 13) = 6" with the 10 coming from the fact that decimal numbers (as the name implies) use base 10. "Multiplicative order" is often shortened to just "order".

Another example: In hexadecimal, 1/Dh (that's 1/13 in decimal) = 0.13B13B13B...h, where the three hex digits "13B" repeat forever. So the order of 16 (mod 13) = 3.

In Mathematica, it's implemented as MultiplicativeOrder[y,x].

Thanks in advance to anybody who has already programmed their Prime to find the order of Y (mod X). It shouldn't be too hard, since Prime has EULER, IDIVIS, and MODPOW built in.

Are you only interested in integer values of X & Y?

Gerald H · (This post was last modified: 02-27-2015 10:21 AM by Gerald H.)

IF you're only interested in integer values for X & Y, this 50G prog does the job:

Input:

2: Modulus

1: Number whose orderis to be calculated

Returns the order you requested.

::
CK2&Dispatch
# FFFF
::
2DUP
FPTR2 ^ZGCDext
FPTR2 ^ZIsOne?
NOTcase2drop
Z0_
OVER
FPTR2 ^QMod
DUPUNROT
OVER
FPTR2 ^EULER
FPTR2 ^ZFACTO
ROTDROP
DUPLENCOMP
#2/
ZERO_DO
DUPUNROT
INDEX@
#2*
#1+DUP
#1+
SUBCOMP
INCOMPDROP
OVERUNROT
COERCE
FPTR2 ^PPow#
ROTSWAP
FPTR2 ^ZQUOText
4ROLLOVER
6PICK
FPTR2 ^ModPow
5PICK
FPTR2 ^QMod
BEGIN
FPTR2 ^DupZIsOne?
NOT_WHILE
::
3PICK
6PICK
FPTR2 ^ModPow
5PICK
FPTR2 ^QMod
SWAP3PICK
FPTR2 ^QMul
SWAP
;
REPEAT
DROPSWAPDROP
4PICKSWAP
ROT
LOOP
DROP
4UNROLL3DROP
;
;

I'm sure you Prime buffs won't have much trouble translating that into Prime.

**rprosperi** · 02-27-2015, 01:55 PM

(02-27-2015 09:57 AM)Gerald H Wrote: I'm sure you Prime buffs won't have much trouble translating that into Prime.

LOL

Joe Horn · 02-27-2015, 04:01 PM

(02-27-2015 08:49 AM)Thomas Ritschel Wrote: Here is a simple non-CAS variant:

Thanks, Thomas! Now I gotta turn your program into an exact-integer CAS program.

(02-27-2015 09:57 AM)Gerald H Wrote: IF you're only interested in integer values for X & Y, this 50G prog does the job: ...

Here's the URPL program I currently use on the 50g:

Code:

<<

WHILE DUP PICK3 GCD DUP 1 >

REPEAT /

END DROP DUP MODSTO EULER DIVIS DUP2 POWMOD 1 POS GET NIP

>>

BYTES: 11.5 #F350h
Input: Y, X (exact mode, of course)
Output: order of Y (mod X)

Gerald H · (This post was last modified: 02-27-2015 04:38 PM by Gerald H.)

(02-27-2015 04:01 PM)Joe Horn Wrote:
(02-27-2015 08:49 AM)Thomas Ritschel Wrote: Here is a simple non-CAS variant:

Thanks, Thomas! Now I gotta turn your program into an exact-integer CAS program.

(02-27-2015 09:57 AM)Gerald H Wrote: IF you're only interested in integer values for X & Y, this 50G prog does the job: ...

Here's the URPL program I currently use on the 50g:

Code:

<< WHILE DUP PICK3 GCD DUP 1 > REPEAT / END DROP DUP MODSTO EULER DIVIS DUP2 POWMOD 1 POS GET NIP >>
BYTES: 11.5 #F350h
Input: Y, X (exact mode, of course)
Output: order of Y (mod X)

Nice, but the POWMOD is a very heavy calculation for, eg 777 mod 541*10007 takes about 5 sec with your prog.

Gerald H · 02-28-2015, 07:30 AM

(02-27-2015 04:01 PM)Joe Horn Wrote:
(02-27-2015 08:49 AM)Thomas Ritschel Wrote: Here is a simple non-CAS variant:

Thanks, Thomas! Now I gotta turn your program into an exact-integer CAS program.

(02-27-2015 09:57 AM)Gerald H Wrote: IF you're only interested in integer values for X & Y, this 50G prog does the job: ...

Here's the URPL program I currently use on the 50g:

Code:

<< WHILE DUP PICK3 GCD DUP 1 > REPEAT / END DROP DUP MODSTO EULER DIVIS DUP2 POWMOD 1 POS GET NIP >>
BYTES: 11.5 #F350h
Input: Y, X (exact mode, of course)
Output: order of Y (mod X)

& thanks for publishing your programme, it made me question the structure of mine. I've now incorporated removing the common factors at the start instead of the crazy return zero. Lord knows why I did that!

Gerald H · 02-28-2015, 09:39 AM

(02-28-2015 07:30 AM)Gerald H Wrote:
(02-27-2015 04:01 PM)Joe Horn Wrote: Thanks, Thomas! Now I gotta turn your program into an exact-integer CAS program.

Here's the URPL program I currently use on the 50g:

Code:

<< WHILE DUP PICK3 GCD DUP 1 > REPEAT / END DROP DUP MODSTO EULER DIVIS DUP2 POWMOD 1 POS GET NIP >>
BYTES: 11.5 #F350h
Input: Y, X (exact mode, of course)
Output: order of Y (mod X)

& thanks for publishing your programme, it made me question the structure of mine. I've now incorporated removing the common factors at the start instead of the crazy return zero. Lord knows why I did that!

Dear Gerald,

I write to you to encourage you in your endeavours & to correct you.

Your programme is correct & Joe Horn's erroneous.

Try the order of 777 modulo 3600, then raise 777 to that power mod 3600 - is the answer one?

You just have too much respect for that no-good Joe Horn & too little confidence in yourself.

& remember Robert Record's words on Ptolemy.

I know you will come to the right conclusion,

For I am

A Gerald From The Future.

Joe Horn · 02-28-2015, 01:14 PM

(02-28-2015 09:39 AM)Gerald H Wrote: Your programme is correct & Joe Horn's erroneous.

Try the order of 777 modulo 3600, then raise 777 to that power mod 3600 - is the answer one?

You just have too much respect for that no-good Joe Horn & too little confidence in yourself.

Mathematica's MultiplicativeOrder(777,3600) does not return an answer, because 777 and 3600 are not coprime. But MultiplicativeOrder(777/3,3600) returns 60... same as my program. I'm just guessing, but perhaps this means that the GCD should be removed from the first input rather than the second, like this:

Code:

<<

SWAP WHILE DUP PICK3 GCD DUP 1 >

REPEAT /

END DROP SWAP DUP MODSTO EULER DIVIS DUP2 POWMOD 1 POS GET NIP

>>

Gerald H · 02-28-2015, 01:56 PM

(02-28-2015 01:14 PM)Joe Horn Wrote:
(02-28-2015 09:39 AM)Gerald H Wrote: Your programme is correct & Joe Horn's erroneous.

Try the order of 777 modulo 3600, then raise 777 to that power mod 3600 - is the answer one?

You just have too much respect for that no-good Joe Horn & too little confidence in yourself.

Mathematica's MultiplicativeOrder(777,3600) does not return an answer, because 777 and 3600 are not coprime. But MultiplicativeOrder(777/3,3600) returns 60... same as my program. I'm just guessing, but perhaps this means that the GCD should be removed from the first input rather than the second, like this:

Code:

<< SWAP WHILE DUP PICK3 GCD DUP 1 > REPEAT / END DROP SWAP DUP MODSTO EULER DIVIS DUP2 POWMOD 1 POS GET NIP >>

No, the meaning is that if GCD of the two numbers is greater than one then NO power of that number is equal to one modulo the 2nd number.

Joe Horn · 03-01-2015, 01:21 AM

(02-28-2015 01:56 PM)Gerald H Wrote: No, the meaning is that if GCD of the two numbers is greater than one then NO power of that number is equal to one modulo the 2nd number.

Understood. But what I'm looking for is "the period of 1/X in base Y". It's only slowly dawning on me that this is NOT the same as "the order of Y mod X". Wolfram Mathworld says, "The number of digits in the repeating portion of the decimal expansion of a rational number can also be found directly from the multiplicative order of its denominator." But that assumes that the multiplicative order of the denominator exists, which apparently is not true, even when it *is* a repeating decimal. Example: 1/14 is a repeating decimal with a period of 6, and that's why my program returns 6 for an input of 10 & 14. But Mathematica's MultiplicativeOrder(10,14) refuses to return an answer for the reason you cited (10 and 14 are not coprime), just like Thomas' Prime program (which runs forever until halted by the user). So, how would you suggest calculating the period of the repeating decimal of 1/x where x is not coprime with 10?

Please accept my apology if it seems like I'm changing the subject, which I might be doing inadvertently! When I started this thread, I had thought that "period of 1/x base y" was the same as "order of y mod x" once the GCD of x and y was removed from x (which is why my program starts by removing the GCD). That's certainly true when y=10. Can it be false for y<>10? Thanks in advance for teaching this student who is always eager to learn.

Gerald H · (This post was last modified: 03-01-2015 07:29 AM by Gerald H.)

(03-01-2015 01:21 AM)Joe Horn Wrote:
(02-28-2015 01:56 PM)Gerald H Wrote: No, the meaning is that if GCD of the two numbers is greater than one then NO power of that number is equal to one modulo the 2nd number.

Understood. But what I'm looking for is "the period of 1/X in base Y". It's only slowly dawning on me that this is NOT the same as "the order of Y mod X". Wolfram Mathworld says, "The number of digits in the repeating portion of the decimal expansion of a rational number can also be found directly from the multiplicative order of its denominator." But that assumes that the multiplicative order of the denominator exists, which apparently is not true, even when it *is* a repeating decimal. Example: 1/14 is a repeating decimal with a period of 6, and that's why my program returns 6 for an input of 10 & 14. But Mathematica's MultiplicativeOrder(10,14) refuses to return an answer for the reason you cited (10 and 14 are not coprime), just like Thomas' Prime program (which runs forever until halted by the user). So, how would you suggest calculating the period of the repeating decimal of 1/x where x is not coprime with 10?

Please accept my apology if it seems like I'm changing the subject, which I might be doing inadvertently! When I started this thread, I had thought that "period of 1/x base y" was the same as "order of y mod x" once the GCD of x and y was removed from x (which is why my program starts by removing the GCD). That's certainly true when y=10. Can it be false for y<>10? Thanks in advance for teaching this student who is always eager to learn.

For that you should read this:

http://mathworld.wolfram.com/DecimalExpansion.html

I have edited out my misleading comment.

Gerald H · 03-01-2015, 08:18 AM

ie Write fraction in lowest terms, a/b, remove factors of 2 & 5 from b, call this c, then calculate order of 10 modulo c - that, I hope, does the trick, ie returns number of repeating digits.

Gerald H · (This post was last modified: 03-01-2015 09:17 AM by Gerald H.)

& here the prog to do it:

::
CK2&Dispatch
# FFFF
::
FPTR2 ^ZTrialDiv2
DROP
BEGIN
DUP
Z5_
FPTR2 ^ZMod
FPTR2 ^QIsZero?
WHILE
::
Z5_
FPTR2 ^ZQUOText
;
REPEAT
FPTR2 ^DupZIsOne?
case2drop
Z0_
DUPUNROT
FPTR2 ^ZGCDext
FPTR2 ^ZQUOText
Z10_
xORD (name for my prog above)
;
;

Again, I leave Prime translation to the experts.

Gerald H · 03-01-2015, 09:48 AM

But this prog is better:

::
CK2&Dispatch
# FFFF
::
FPTR2 ^ZTrialDiv2
DROP
BEGIN
DUP
Z5_
FPTR2 ^ZMod
FPTR2 ^QIsZero?
WHILE
::
Z5_
FPTR2 ^ZQUOText
;
REPEAT
DUPUNROT
FPTR2 ^ZGCDext
FPTR2 ^ZQUOText
FPTR2 ^DupZIsOne?
casedrop
Z0_
Z10_
xORD
;
;

Joe Horn · (This post was last modified: 03-01-2015 05:43 PM by Joe Horn.)

(02-27-2015 09:57 AM)Gerald H Wrote: IF you're only interested in integer values for X & Y, this 50G prog does the job: ...

Z0_

...

The 9th line of your program won't compile using the built-in tools. What is Z0_?

EDIT: Never mind, I figured out it means ZINT 0. What assembler is that for?

Joe Horn · 03-01-2015, 06:17 PM

(03-01-2015 09:48 AM)Gerald H Wrote: But this prog is better: ...

Uh oh. Running it after 12 ENTER 23 yields 22, but the correct answer for the period of 1/23 in base 12 (as returned by my URPL program above) is 11, as can be seen by actually writing 1/23 in base 12:

0.06316948421 06316948421 06316948421 06316948421 ...

Am I misunderstanding something here? It happens. Thanks in advance for your patience.

Disclaimer: My program is correct not based on any personal authority which I neither have nor have ever claimed to have, but it SEEMS TO ME to be correct based on empirical data. I only mention this due to some creepy and cryptic references recently made here and in the General Software Library about the danger of giving credence to anybody based on authority.

Gerald H · 03-01-2015, 07:02 PM

(03-01-2015 06:17 PM)Joe Horn Wrote:
(03-01-2015 09:48 AM)Gerald H Wrote: But this prog is better: ...

Uh oh. Running it after 12 ENTER 23 yields 22, but the correct answer for the period of 1/23 in base 12 (as returned by my URPL program above) is 11, as can be seen by actually writing 1/23 in base 12:

0.06316948421 06316948421 06316948421 06316948421 ...

Am I misunderstanding something here? It happens. Thanks in advance for your patience.

Disclaimer: My program is correct not based on any personal authority which I neither have nor have ever claimed to have, but it SEEMS TO ME to be correct based on empirical data. I only mention this due to some creepy and cryptic references recently made here and in the General Software Library about the danger of giving credence to anybody based on authority.

Don't understand why you're doing the calculation in base 12 - my prog is only good for base 10 representation. Entering 12 & 23 returns length of period of 12/23 in base 10.

Nothing "creepy or cryptic" - I just have too much respect for you. You have produced excellent progs for years & I'm very impressed & more readily impute error to myself than you.

I'm not the only one affected by this respect for the greats, Robert Record's words are a lighthouse for us all.

Joe Horn · 03-01-2015, 09:55 PM

(03-01-2015 07:02 PM)Gerald H Wrote: Don't understand why you're doing the calculation in base 12 - my prog is only good for base 10 representation. Entering 12 & 23 returns length of period of 12/23 in base 10.

As I mentioned in the original posting, I'm looking for the period of the repeating "decimal" expansion of 1/Y in base X. The example I gave there was 1/13 in hex, so Y=13, X=16 (1/Dh = 0.13B13B13B...h) which has a period of 3. I'm looking for a program that handles any base, not just decimal and hex. I think that my URPL program does this, but it's much slower than your ORD program, so I greatly appreciate all your insights here.

(03-01-2015 07:02 PM)Gerald H Wrote: Nothing "creepy or cryptic" - I just have too much respect for you. You have produced excellent progs for years & I'm very impressed & more readily impute error to myself than you.

I'm not the only one affected by this respect for the greats, Robert Record's words are a lighthouse for us all.

We're all in the same boat. Putting anybody on too high a pedestal can capsize the boat. Wink