Comments on Print the modular multiplicative inverse / virtual fractions

Post

Print the modular multiplicative inverse / virtual fractions

−1

Goal

Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.

Example output

Print these values (or an extension of them):

Rules

Use a modulus of at least $65536 = 2^{16}$. But you can use any modulus $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
Print the modular multiplicative inverse for at least all the natural, odd values $<98$.
You can print it in any normal base.
You can print additional stuff, but it should be clear which parts belong to the modular multiplicative inverse and which do not.
Your program should print the required output in less than 1 hour on a modern PC (or other hardware that is affordable).

Ungolfed example

#!/usr/bin/env python3

# Calculates the modular multiplicative inverse
def imod(a, n):
  c=1
  while c % a:
    c+=n
  return c//a

# Print the multiplicative inverse for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
  b = imod(i,n)
  print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))

Why these numbers are interesting

You don't have to understand this part in order to participate in the challenge.

There are multiple ways to look at these numbers. All lead to the same numbers. I call them virtual fractions (made up term). Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).

Example for 1/3

For example, you have the 16 bit unsigned integer with the value 0xAAAB (43691). You can multiply it with 3 and get 1.

  3 * 0xAAAB  =  3 * 0b1010 1010 1010 1011  =  3 * 43691
  =  0x20001  =   0b10 0000 0000 0000 0001  =     131073
Storing it in a 16 bit variable drops the 1 at bit 17:
  =   0x0001  =      0b0000 0000 0000 0001  =          1

This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be 1%65536 == 43691%65536 or 1&0xFFFF == 43691&0xFFFF in C). This is interesting because that is what a 16-Bit ALU would do when it multiples 0xAAABu * 3u. Therefore, 0xAAAB is like $1/3$.

There are other ways to look at these numbers, but that should be enough for this challenge.

code-golf math

posted 10 months ago

CC BY-SA 4.0

10mo ago by trichoplax‭

H_H‭

110 reputation 6 6 11 52

Raw

Markdown

History

is a duplicate

This question has been asked before and has already been answered. It should be marked as a duplicate.

Please enter the URL of the proposed duplicate in the details field below.

not constructive

This question cannot be answered in a way that is helpful to anyone. It's not possible to learn something from possible answers, except for the solution for the specific problem of the asker.

−0

[Pyth], 16 bytes .^RtJ^ …

9mo ago

1 comment thread

Way too confusing (9 comments)

Olin Lathrop‭ wrote 10 months ago

copy link

"Virtual fractions are integers" - A fraction is inherently two numbers. You even talk of a numerator and denominator.

Your example (43691 * 3) mod 65536 = 1 doesn't explain much. Where did the 3 come from?

The equation 3 * 43691 = 1 mod 65536 is just plain wrong. 1 mod 65536 is 1, but 3 * 43691 is clearly not 1.

"a p-adic/2-adic number" - Huh? What?

"only print the ones with a numerator of 1" - So all the "fractions" we're supposed to print are 1/n where N is 1-65535? Your example output shows integers, not fractions. So we're supposed to print the denominators of these fractions?

"you can multiply them with the denominator and you get the numerator" - That's true of any fraction.

H_H‭ wrote 10 months ago · edited 10 months ago

copy link

Thank you for your feedback.

Ok, i should have used a ≡ instead of a =. For the rest, i probably explained it a bit too complicated. Maybe you didn't learn about that branch of mathematics and that is where the confusion comes from (which i also had in some challenges from other people) or i did explain it in a wrong way.

The wrong symbol first:

$ X ≡ Y \mod A $ in C code means: X%A == Y%A and not X == Y%A. You apply the modulus on both sides of the identicalsign. That means $3 \cdot 43691 ≡ 1 \mod 65536$ is the same formula as $1 ≡ 3 \cdot 43691 \mod 65536$. Maybe i will change the order to make it easier to understand. When you type 3 * 43691 = 1 mod 65536 in Wolframα, you get True, despite using a = instead of a ≡: https://www.wolframalpha.com/input?i=3+*+43691+%3D+1+mod+65536

You can read more about here: https://de.wikipedia.org/wiki/Kongruenz_(Zahlentheorie)

1/..

H_H‭ wrote 10 months ago · edited 10 months ago

copy link

The term virtual fraction is one that i created. But fractions with only a single number do exist in Mathematics.

Now there are multiple ways you can look at this challenge. I know at least 3:

Consider a C-function: int a=3; uint16_t f(uint16_t x) { return a*x; } With what value do you need to call f() so that 1 is returned?
What is the modular multiplicative inverse of 3 to the modulo of 65536?
What are the last 16 binary digits of the 2-Adic number for $1/3$?

They all lead to the same result. If you understand one of them you can understand the challenge without needing to know how the other 2 works. Point 1. is probably the easiest to understand for programmers. Point 2. is probably the shortest and easiest to implement. Point 3. is more from a Mathematicians point of view.

Some details about the individual ways:

2/...

H_H‭ wrote 10 months ago · edited 10 months ago

copy link

To 1.: In this example, with a==3, you would have to call f() with the value 43691 or 0xAAAB. Because 3 * 0xAAAB results in 0x20001. And since we only return a 16 bit variable, the 0x2 at the beginning is droped. That means f(0xAAAB) will return 1. Now think about which argument we need when a==1, a==3, a==5, a==7, ... so that f() will return a 1.

To 2: The modular multiplicative inverse with a modulos of $65536$ or $0x10000$ for 3 is 43691. Because $3 \cdot 43691 ( \mod 65536 ) = 131073 ( \mod 65536 ) = 1$. Now calculate the modular multiplicative inverse for 1, 3, 5, 7, ..., with a modulos of $65536$. Many libraries have functions to calculate the modular multiplicative inverse, such as pow(a,-1,65536) in Python.

3/..

H_H‭ wrote 10 months ago · edited 10 months ago

copy link

To 3: A P-adic-number is one that has an infinite amount of digits to the left of the "decimal"-comma/point (instead of the right). Normally you would choose a prime number as base, such as base 2 or base 3 and not 10, this is why there is a P in P-adic. But lets make an example with base 10, a 10-adic number:

Lets consider the 10-adic number: $...66666667$, it has an infinite amount of 6 to the left. Try to multiple this number by 3 and you get $...000001$, with a infinite amount of 0 to the left. Since we can ignore 0 in front of a number, this number is equal to $1$. So $...66666667 \cdot 3 $ is really 1. With that $...66666667$ is equal to $1/3$. And yes, this really works (it breaks with base 10, but it does not with a prime base. And you can add and multiple P-adics).

We can't use a infinite amount of digits in real hardware, therefore we limit the P-adics to just 16 binary digits for this challenge.

Sorry for the long answer, but i hoped it makes it easier to understand.

trichoplax‭ wrote 10 months ago

copy link

This appears to be an interesting challenge, wrapped up in an interesting but unnecessary concept. The challenge would work without the concept, and be understood by more people.

For this reason, my personal preference would be to have the simple statement of the problem at the start of the challenge, so anyone can answer regardless of their background knowledge.

Then at the end of the challenge wording there can be a section for interesting related topics, perhaps split into a subsection for each of the 3 interpretations you describe here. This way the challenge is the golfing, rather than understanding what is being asked.

I'm not against the idea of a challenge where working out what the question means as a puzzle is part of it, but since you are taking the time to explain things here, this doesn't seem like that sort of challenge.

In general I prefer a short clear specification at the start of a challenge, followed by examples at the end.

trichoplax‭ wrote 10 months ago

copy link

I find this much more clear. Potential improvements:

The explanation section at the end could be broken up with subheadings or a numbered list.
The heading "Explanation" might be better changed to something that makes immediately clear that this section is optional. Perhaps "Background" or "Related".
Standard terms such as p-adic numbers could link to a source like Wikipedia on first mention to make clear that they are standard.
Terms that are not standard (such as virtual fractions) could be in bold italics on first mention and made clear that they are being introduced as new terms for this challenge.
Some of the sentences could be made less ambiguous by changing the word order and avoiding abbreviations (such as "h" for "hour").
There are some typos.

Once you've made any edits you want to, I'm happy to make a suggested edit for typos and ambiguity if you like. I will avoid this until you have finished your own edits.

Communities

Comments on Print the modular multiplicative inverse / virtual fractions

Print the modular multiplicative inverse / virtual fractions

Goal

Example output

Rules

Ungolfed example

Why these numbers are interesting

Example for 1/3

1 comment thread