Relatively prime integers in NumPy

[Popov, Dmitry Yu]

Dear Sirs.

Does NumPy provide a simple mechanism to identify relatively prime integers, i.e. integers which don't have a common factor other than +1 or -1? For example, in case of this array:
[[1,5,8],
[2,4,8],
[3,3,9]]
I can imagine a function which would return array of common factors along axis 0: [1,2,3]. Those triples of numbers along axis 1 with the factor of1 or -1 would be relatively prime integers.

Regards,
Dmitry Popov

Argonne, IL
USA

[a***@gmail.com]

Дмитрий,

You may think you explained what you wanted but I do not see what result you
expect from your examples.

Your request is a bit too esoteric to be a great candidate for being built
into a module like numpy for general purpose se but I can imagine it could
be available in modules build on top of numpy.

Is there a reason you cannot solve this mostly outside numpy?

It looks like you could use numpy to select the numbers you want to compare,
then call one of many methods you can easily search for to see how to use
python to make some list or other data structure for divisors of each number
involved and then use standard methods to compare the lists and exact common
divisors. If needed, you could then put the results back into your original
data structure using numpy albeit the number of matches can vary.

Maybe a better explanation is needed as I cannot see what your latter words
about -1 and 1 are about. Perhaps someone else knows.




-----Original Message-----
From: Python-list <python-list-bounces+avi.e.gross=***@python.org> On
Behalf Of Popov, Dmitry Yu via Python-list
Sent: Monday, July 8, 2024 3:10 PM
To: Popov, Dmitry Yu via Python-list <python-***@python.org>
Subject: Relatively prime integers in NumPy

Dear Sirs.

Does NumPy provide a simple mechanism to identify relatively prime integers,
i.e. integers which don't have a common factor other than +1 or -1? For
example, in case of this array:
[[1,5,8],
[2,4,8],
[3,3,9]]
I can imagine a function which would return array of common factors along
axis 0: [1,2,3]. Those triples of numbers along axis 1 with the factor of1
or -1 would be relatively prime integers.

Regards,
Dmitry Popov

Argonne, IL
USA

[Paul Rubin]

Post by a***@gmail.com
python to make some list or other data structure for divisors of each number
involved

Two numbers a and b are coprime if math.gcd(a,b) == 1, I am pretty sure.
That is true by definition(?) when a and b are both > 0. Experiment
indicates it seems to work even when one or both of a and b are
negative, but I don't have a proof and haven't examined the
implementation. I don't know how gcd is mathematically defined in that
situation.

[Lawrence D'Oliveiro]

Post by Paul Rubin
Two numbers a and b are coprime if math.gcd(a,b) == 1, I am pretty sure.
That is true by definition(?) when a and b are both > 0. Experiment
indicates it seems to work even when one or both of a and b are
negative, but I don't have a proof and haven't examined the
implementation. I don't know how gcd is mathematically defined in that
situation.

You can derive the answer quite trivially by observing that negative
numbers are smaller (less than, not greater than) positive numbers.

[Oscar Benjamin]

(posting on-list this time)

On Thu, 11 Jul 2024 at 15:18, Popov, Dmitry Yu via Python-list

Post by Popov, Dmitry Yu
Dear Sirs.
[[1,5,8],
[2,4,8],
[3,3,9]]
I can imagine a function which would return array of common factors along axis 0: [1,2,3]. Those triples of numbers along axis 1 with the factor of1 or -1 would be relatively prime integers.

It sounds like you want the gcd (greatest common divisor) of each row.
The math module can do this:

In [1]: a = [[1,5,8],
...: [2,4,8],
...: [3,3,9]]

In [2]: import math

In [3]: [math.gcd(*row) for row in a]
Out[3]: [1, 2, 3]

NumPy can also do it apparently:

In [10]: np.gcd.reduce(np.transpose(a))
Out[10]: array([1, 2, 3])

https://en.wikipedia.org/wiki/Greatest_common_divisor

--
Oscar

[a***@gmail.com]

OK. That explains a bit more.



If I understand what you are looking for is a fast implementation and quite often in Pyhon it means using code written in another language such as C that is integrated carefully in a moule or two. Another tack is to replace many explicit loops with often much faster vectorized operations. Numpy provides advantages like the above if you use it as intended.



Of course there are other techniques in how code is refactored or the order of operations, or doing things in parallel.



Just as an example, your inner loop ear the top is operating one at a time or numbers between 0 and max_l and hen creates variables initialized and then possibly changed in chvec and maxmult. It uses various conditions to change those variables then goes on to do more things included in a fourth nested loop.



What would happen if, instead, you used two objects with the same names that were each a numpy array, or perhaps combined into a dataframe type object?



Using numpy (and perhaps pandas) you could have code that initialized one such array to hold the initial 1 or 2 as needed in an object whose length was max_l+1 and then the next operations, using numpy notation would be along the lines of replace the corresponding value depending on external variables you call h or k and so on.



There would be several invisible loops, perhaps chained in some way, but probably running way faster than the explicit loop.



I am not going to write any specific code, but suggest you read some documentation on how to use numpy for some of the operations you want when operating on larger clusters of info. You can gain some speed even by changing a few parts. To refactor the entire thing would take more thought and if you come up with the idea of operating on a multidimensional array, might take some care.



But consider what would happen if you looked at your loops which are currently of a fixed size and created a 3-D matrix with dimensions of max_h+1, max_k+1, and max_l+1 and simply initialized it with all possible initial values and then ran an algorithm to manipulate it, often asking numpy for various slices or whatever works for you as in axes. This architecture may not work for ou but is an example of the kind of thinking it an take to make a problem use algorithms more efficiently.



I note the code did not actually help me understand what mathematical operation you want to perform. I assumed I might see some operations like division and t may be other parts of your code that implement what you want.



But if this is a common enough need, I suspect you may want to see if something similar enough is out there. Your code may be more complex and more like the sieve of Eratosthenes that attempts to test every possibility.



One algorithm I have seen simply takes the numbers you are evaluating and in a loop of the first N primes (or an open-ended generator) simply does an integer division by 2, as many times as it returns an integral result, then as many divisions by 3 then 5 and 7 and so on. It aborts when it has been chopped down to size, or the prime being used is large enough (square root or so) ad at the end, you should have some sequence of divisors, or just and the number if it is prime. Some such algorithm can be fairly fast and perhaps can even be done vectorized.



One last comment is about memoization. If your data is of a nature where a relatively few numbers come up often, then you an use something, like perhaps a dictionary, to store the results of a computation like getting a list of prime factors for a specific number, or just recording whether it is prime or composite. Later calls to do calculations would always check if the result has already been saved and skip recalculating it.



Good Luck





From: Popov, Dmitry Yu <***@anl.gov>
Sent: Thursday, July 11, 2024 3:26 PM
To: ***@gmail.com; 'Popov, Dmitry Yu via Python-list' <python-***@python.org>
Subject: Re: Relatively prime integers in NumPy



Thank you for your interest. My explanation is too concise indeed, sorry. So far, I have used Python code with three enclosed 'for' loops for this purpose which is pretty time consuming. I'm trying to develop a NumPy based code to make this procedure faster. This routine is kind of 'heart' of the algorithm to index of X-ray Laue diffraction patterns. In our group we have to process huge amount of such patterns. They are collected at a synchrotron radiation facility. Faster indexation routine would help a lot.



This is the code I'm currently using. Any prompts how to implement it in NumPy would be highly appreciated.



for h in range(0, max_h):

      for k in range(0, max_k):

            for l in range(0, max_l):

                  chvec=1

                  maxmult=2

                  if h > 1:                     

                        maxmult=h

                  if k > 1:

                        maxmult=k

                  if l > 1:

                        maxmult=l

                  if h > 1:

                        if maxmult > h:

                              maxmult=h

                  if k > 1:

                        if maxmult > k:

                              maxmult=k

                  if l > 1:

                        if maxmult > l:

                              maxmult=l

                  maxmult=maxmult+1

                  for innen in range(2, maxmult):

                        if h in range(0, (max_h+1), innen):

                              if k in range(0, (max_k+1), innen):

                                    if l in range(0, (max_l+1), innen):

                                          chvec=0

                  if chvec==1:

                        # Only relatively prime integers h,k,l pass to this block of the code





_____

From: ***@gmail.com <mailto:***@gmail.com> <***@gmail.com <mailto:***@gmail.com> >
Sent: Thursday, July 11, 2024 1:22 PM
To: Popov, Dmitry Yu <***@anl.gov <mailto:***@anl.gov> >; 'Popov, Dmitry Yu via Python-list' <python-***@python.org <mailto:python-***@python.org> >
Subject: RE: Relatively prime integers in NumPy



Дмитрий, You may think you explained what you wanted but I do not see what result you expect from your examples. Your request is a bit too esoteric to be a great candidate for being built into a module like numpy for general purpose se but

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender

This message came from outside your organization.



ZjQcmQRYFpfptBannerEnd

Дмитрий,

You may think you explained what you wanted but I do not see what result you
expect from your examples.

Your request is a bit too esoteric to be a great candidate for being built
into a module like numpy for general purpose se but I can imagine it could
be available in modules build on top of numpy.

Is there a reason you cannot solve this mostly outside numpy?

It looks like you could use numpy to select the numbers you want to compare,
then call one of many methods you can easily search for to see how to use
python to make some list or other data structure for divisors of each number
involved and then use standard methods to compare the lists and exact common
divisors. If needed, you could then put the results back into your original
data structure using numpy albeit the number of matches can vary.

Maybe a better explanation is needed as I cannot see what your latter words
about -1 and 1 are about. Perhaps someone else knows.




-----Original Message-----
From: Python-list <python-list-bounces+avi.e.gross=***@python.org <mailto:python-list-bounces+avi.e.gross=***@python.org> > On
Behalf Of Popov, Dmitry Yu via Python-list
Sent: Monday, July 8, 2024 3:10 PM
To: Popov, Dmitry Yu via Python-list <python-***@python.org <mailto:python-***@python.org> >
Subject: Relatively prime integers in NumPy

Dear Sirs.

Does NumPy provide a simple mechanism to identify relatively prime integers,
i.e. integers which don't have a common factor other than +1 or -1? For
example, in case of this array:
[[1,5,8],
[2,4,8],
[3,3,9]]
I can imagine a function which would return array of common factors along
axis 0: [1,2,3]. Those triples of numbers along axis 1 with the factor of1
or -1 would be relatively prime integers.

Regards,
Dmitry Popov

Argonne, IL
USA

--
https://urldefense.us/v3/__https://mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!ZGK1ZXYgmC6cpNa1xTXVTNklhunjYiinwaDe_xE3sJyVs4ZcVgUB_v2FKvDzDspx7IzFCZI7JpFsiV5iH58P$ <https://urldefense.us/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!ZGK1ZXYgmC6cpNa1xTXVTNklhunjYiinwaD

[Paul Rubin]

Post by a***@gmail.com
make some list or other data structure for divisors of each number
involved and then use standard methods to compare the lists and exact
common divisors.

You don't need to find divisors (factor the numbers) to find the gcd.
Factorization can be very slow. Gcd on the other hand is very fast,
using the Euclidean GCD algorithm. You should be able to find info
about this easily. Factorization would be a terrible way to compute
gcd's.

[Peter J. Holzer]

Post by Popov, Dmitry Yu
Does NumPy provide a simple mechanism to identify relatively prime
integers, i.e. integers which don't have a common factor other than +1
or -1?

Typing "numpy gcd" into my favourite search engine brings me to https://numpy.org/doc/stable/reference/generated/numpy.gcd.html

hp

[Popov, Dmitry Yu]

Thank you for your interest. My explanation is too concise indeed, sorry. So far, I have used Python code with three enclosed 'for' loops for this purpose which is pretty time consuming. I'm trying to develop a NumPy based code to make this procedure faster. This routine is kind of 'heart' of the algorithm to index of X-ray Laue diffraction patterns. In our group we have to process huge amount of such patterns. They are collected at a synchrotron radiation facility. Faster indexation routine would help a lot.

This is the code I'm currently using. Any prompts how to implement it in NumPy would be highly appreciated.

for h in range(0, max_h):
      for k in range(0, max_k):
            for l in range(0, max_l):
                  chvec=1
                  maxmult=2
                  if h > 1:                     
                        maxmult=h
                  if k > 1:
                        maxmult=k
                  if l > 1:
                        maxmult=l
                  if h > 1:
                        if maxmult > h:
                              maxmult=h
                  if k > 1:
                        if maxmult > k:
                              maxmult=k
                  if l > 1:
                        if maxmult > l:
                              maxmult=l
                  maxmult=maxmult+1
                  for innen in range(2, maxmult):
                        if h in range(0, (max_h+1), innen):
                              if k in range(0, (max_k+1), innen):
                                    if l in range(0, (max_l+1), innen):
                                          chvec=0
                  if chvec==1:
                        # Only relatively prime integers h,k,l pass to this block of the code


________________________________
From: ***@gmail.com <***@gmail.com>
Sent: Thursday, July 11, 2024 1:22 PM
To: Popov, Dmitry Yu <***@anl.gov>; 'Popov, Dmitry Yu via Python-list' <python-***@python.org>
Subject: RE: Relatively prime integers in NumPy

Дмитрий, You may think you explained what you wanted but I do not see what result you expect from your examples. Your request is a bit too esoteric to be a great candidate for being built into a module like numpy for general purpose se but
ZjQcmQRYFpfptBannerStart
This Message Is From an External Sender
This message came from outside your organization.

ZjQcmQRYFpfptBannerEnd

Дмитрий,

You may think you explained what you wanted but I do not see what result you
expect from your examples.

Your request is a bit too esoteric to be a great candidate for being built
into a module like numpy for general purpose se but I can imagine it could
be available in modules build on top of numpy.

Is there a reason you cannot solve this mostly outside numpy?

It looks like you could use numpy to select the numbers you want to compare,
then call one of many methods you can easily search for to see how to use
python to make some list or other data structure for divisors of each number
involved and then use standard methods to compare the lists and exact common
divisors. If needed, you could then put the results back into your original
data structure using numpy albeit the number of matches can vary.

Maybe a better explanation is needed as I cannot see what your latter words
about -1 and 1 are about. Perhaps someone else knows.




-----Original Message-----
From: Python-list <python-list-bounces+avi.e.gross=***@python.org> On
Behalf Of Popov, Dmitry Yu via Python-list
Sent: Monday, July 8, 2024 3:10 PM
To: Popov, Dmitry Yu via Python-list <python-***@python.org>
Subject: Relatively prime integers in NumPy

Dear Sirs.

Does NumPy provide a simple mechanism to identify relatively prime integers,
i.e. integers which don't have a common factor other than +1 or -1? For
example, in case of this array:
[[1,5,8],
[2,4,8],
[3,3,9]]
I can imagine a function which would return array of common factors along
axis 0: [1,2,3]. Those triples of numbers along axis 1 with the factor of1
or -1 would be relatively prime integers.

Regards,
Dmitry Popov

Argonne, IL
USA

[Popov, Dmitry Yu]

Thank you very much, Oscar.

Using the following code looks like a much better solution than my current Python code indeed.

np.gcd.reduce(np.transpose(a))
or
np.gcd.reduce(a,1)

The next question is how I can generate ndarray of h,k,l indices. This can be easily done from a Python list by using the following code.

import numpy as np
hkl_list=[]
for h in range(0, max_h):
      for k in range(0, max_k):
            for l in range(0, max_l):
                  hkl_local=[]
                  hkl_local.append(h)
                  hkl_local.append(k)
                  hkl_local.append(l)
                  hkl_list.append(hkl_local)
hkl=np.array(hkl_list, dtype=np.int64)

This code will generate a two-dimensional ndarray of h,k,l indices but is it possible to make a faster routine with NumPy?

Regards,
Dmitry




________________________________
From: Python-list <python-list-bounces+dpopov=***@python.org> on behalf of Popov, Dmitry Yu via Python-list <python-***@python.org>
Sent: Thursday, July 11, 2024 2:25 PM
To: ***@gmail.com <***@gmail.com>; 'Popov, Dmitry Yu via Python-list' <python-***@python.org>
Subject: Re: Relatively prime integers in NumPy

Thank you for your interest. My explanation is too concise indeed, sorry. So far, I have used Python code with three enclosed 'for' loops for this purpose which is pretty time consuming. I'm trying to develop a NumPy based code to make this
ZjQcmQRYFpfptBannerStart
This Message Is From an External Sender
This message came from outside your organization.

ZjQcmQRYFpfptBannerEnd

Thank you for your interest. My explanation is too concise indeed, sorry. So far, I have used Python code with three enclosed 'for' loops for this purpose which is pretty time consuming. I'm trying to develop a NumPy based code to make this procedure faster. This routine is kind of 'heart' of the algorithm to index of X-ray Laue diffraction patterns. In our group we have to process huge amount of such patterns. They are collected at a synchrotron radiation facility. Faster indexation routine would help a lot.

This is the code I'm currently using. Any prompts how to implement it in NumPy would be highly appreciated.

for h in range(0, max_h):
      for k in range(0, max_k):
            for l in range(0, max_l):
                  chvec=1
                  maxmult=2
                  if h > 1:                     
                        maxmult=h
                  if k > 1:
                        maxmult=k
                  if l > 1:
                        maxmult=l
                  if h > 1:
                        if maxmult > h:
                              maxmult=h
                  if k > 1:
                        if maxmult > k:
                              maxmult=k
                  if l > 1:
                        if maxmult > l:
                              maxmult=l
                  maxmult=maxmult+1
                  for innen in range(2, maxmult):
                        if h in range(0, (max_h+1), innen):
                              if k in range(0, (max_k+1), innen):
                                    if l in range(0, (max_l+1), innen):
                                          chvec=0
                  if chvec==1:
                        # Only relatively prime integers h,k,l pass to this block of the code


________________________________
From: ***@gmail.com <***@gmail.com>
Sent: Thursday, July 11, 2024 1:22 PM
To: Popov, Dmitry Yu <***@anl.gov>; 'Popov, Dmitry Yu via Python-list' <python-***@python.org>
Subject: RE: Relatively prime integers in NumPy

Дмитрий, You may think you explained what you wanted but I do not see what result you expect from your examples. Your request is a bit too esoteric to be a great candidate for being built into a module like numpy for general purpose se but
ZjQcmQRYFpfptBannerStart
This Message Is From an External Sender
This message came from outside your organization.

ZjQcmQRYFpfptBannerEnd

Дмитрий,

You may think you explained what you wanted but I do not see what result you
expect from your examples.

Your request is a bit too esoteric to be a great candidate for being built
into a module like numpy for general purpose se but I can imagine it could
be available in modules build on top of numpy.

Is there a reason you cannot solve this mostly outside numpy?

It looks like you could use numpy to select the numbers you want to compare,
then call one of many methods you can easily search for to see how to use
python to make some list or other data structure for divisors of each number
involved and then use standard methods to compare the lists and exact common
divisors. If needed, you could then put the results back into your original
data structure using numpy albeit the number of matches can vary.

Maybe a better explanation is needed as I cannot see what your latter words
about -1 and 1 are about. Perhaps someone else knows.




-----Original Message-----
From: Python-list <python-list-bounces+avi.e.gross=***@python.org> On
Behalf Of Popov, Dmitry Yu via Python-list
Sent: Monday, July 8, 2024 3:10 PM
To: Popov, Dmitry Yu via Python-list <python-***@python.org>
Subject: Relatively prime integers in NumPy

Dear Sirs.

Does NumPy provide a simple mechanism to identify relatively prime integers,
i.e. integers which don't have a common factor other than +1 or -1? For
example, in case of this array:
[[1,5,8],
[2,4,8],
[3,3,9]]
I can imagine a function which would return array of common factors along
axis 0: [1,2,3]. Those triples of numbers along axis 1 with the factor of1
or -1 would be relatively prime integers.

Regards,
Dmitry Popov

Argonne, IL
USA

[a***@gmail.com]

Dmitry,



I clearly did not understand what you wanted earlier as you had not made clear that in your example, you already had progressed to some level where you had the data and were now doing a second step. So, I hesitate to say much until either nobody else addressed the issue (as clearly some have) or you explain well enough.



I am guessing you have programming experience in other languages and are not as “pythonic” as some. The code you show may not be quite how others might do it. Some may write mch of your code as a single line of python using a list comprehension such as:



hkl_list = [ [h, k, l] for SOMETHING in RANGE for SOMETHING2 in RANGE2 for SOMETHING3 in RANGE3]



Where h, k. l come from the somethings.



Back to the real world.





From: Popov, Dmitry Yu <***@anl.gov>
Sent: Friday, July 12, 2024 1:13 PM
To: ***@gmail.com; 'Popov, Dmitry Yu via Python-list' <python-***@python.org>; ***@gmail.com; Popov, Dmitry Yu <***@anl.gov>
Subject: Re: Relatively prime integers in NumPy



Thank you very much, Oscar.



Using the following code looks like a much better solution than my current Python code indeed.

np.gcd.reduce(np.transpose(a))
or
np.gcd.reduce(a,1)

The next question is how I can generate ndarray of h,k,l indices. This can be easily done from a Python list by using the following code.

import numpy as np
hkl_list=[]
for h in range(0, max_h):
      for k in range(0, max_k):
            for l in range(0, max_l):
                  hkl_local=[]
                  hkl_local.append(h)
                  hkl_local.append(k)
                  hkl_local.append(l)
                  hkl_list.append(hkl_local)
hkl=np.array(hkl_list, dtype=np.int64)
This code will generate a two-dimensional ndarray of h,k,l indices but is it possible to make a faster routine with NumPy?

Regards,
Dmitry



_____


From: Python-list <python-list-bounces+dpopov=***@python.org <mailto:python-list-bounces+dpopov=***@python.org> > on behalf of Popov, Dmitry Yu via Python-list <python-***@python.org <mailto:python-***@python.org> >
Sent: Thursday, July 11, 2024 2:25 PM
To: ***@gmail.com <mailto:***@gmail.com> <***@gmail.com <mailto:***@gmail.com> >; 'Popov, Dmitry Yu via Python-list' <python-***@python.org <mailto:python-***@python.org> >
Subject: Re: Relatively prime integers in NumPy



Thank you for your interest. My explanation is too concise indeed, sorry. So far, I have used Python code with three enclosed 'for' loops for this purpose which is pretty time consuming. I'm trying to develop a NumPy based code to make this

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender

This message came from outside your organization.



ZjQcmQRYFpfptBannerEnd

Thank you for your interest. My explanation is too concise indeed, sorry. So far, I have used Python code with three enclosed 'for' loops for this purpose which is pretty time consuming. I'm trying to develop a NumPy based code to make this procedure faster. This routine is kind of 'heart' of the algorithm to index of X-ray Laue diffraction patterns. In our group we have to process huge amount of such patterns. They are collected at a synchrotron radiation facility. Faster indexation routine would help a lot.

This is the code I'm currently using. Any prompts how to implement it in NumPy would be highly appreciated.

for h in range(0, max_h):
      for k in range(0, max_k):
            for l in range(0, max_l):
                  chvec=1
                  maxmult=2
                  if h > 1:                     
                        maxmult=h
                  if k > 1:
                        maxmult=k
                  if l > 1:
                        maxmult=l
                  if h > 1:
                        if maxmult > h:
                              maxmult=h
                  if k > 1:
                        if maxmult > k:
                              maxmult=k
                  if l > 1:
                        if maxmult > l:
                              maxmult=l
                  maxmult=maxmult+1
                  for innen in range(2, maxmult):
                        if h in range(0, (max_h+1), innen):
                              if k in range(0, (max_k+1), innen):
                                    if l in range(0, (max_l+1), innen):
                                          chvec=0
                  if chvec==1:
                        # Only relatively prime integers h,k,l pass to this block of the code


________________________________
From: ***@gmail.com <mailto:***@gmail.com> <***@gmail.com <mailto:***@gmail.com> >
Sent: Thursday, July 11, 2024 1:22 PM
To: Popov, Dmitry Yu <***@anl.gov <mailto:***@anl.gov> >; 'Popov, Dmitry Yu via Python-list' <python-***@python.org <mailto:python-***@python.org> >
Subject: RE: Relatively prime integers in NumPy

Дмитрий, You may think you explained what you wanted but I do not see what result you expect from your examples. Your request is a bit too esoteric to be a great candidate for being built into a module like numpy for general purpose se but
ZjQcmQRYFpfptBannerStart
This Message Is From an External Sender
This message came from outside your organization.

ZjQcmQRYFpfptBannerEnd

Дмитрий,

You may think you explained what you wanted but I do not see what result you
expect from your examples.

Your request is a bit too esoteric to be a great candidate for being built
into a module like numpy for general purpose se but I can imagine it could
be available in modules build on top of numpy.

Is there a reason you cannot solve this mostly outside numpy?

It looks like you could use numpy to select the numbers you want to compare,
then call one of many methods you can easily search for to see how to use
python to make some list or other data structure for divisors of each number
involved and then use standard methods to compare the lists and exact common
divisors. If needed, you could then put the results back into your original
data structure using numpy albeit the number of matches can vary.

Maybe a better explanation is needed as I cannot see what your latter words
about -1 and 1 are about. Perhaps someone else knows.




-----Original Message-----
From: Python-list <python-list-bounces+avi.e.gross=***@python.org <mailto:python-list-bounces+avi.e.gross=***@python.org> > On
Behalf Of Popov, Dmitry Yu via Python-list
Sent: Monday, July 8, 2024 3:10 PM
To: Popov, Dmitry Yu via Python-list <python-***@python.org <mailto:python-***@python.org> >
Subject: Relatively prime integers in NumPy

Dear Sirs.

Does NumPy provide a simple mechanism to identify relatively prime integers,
i.e. integers which don't have a common factor other than +1 or -1? For
example, in case of this array:
[[1,5,8],
[2,4,8],
[3,3,9]]
I can imagine a function which would return array of common factors along
axis 0: [1,2,3]. Those triples of numbers along axis 1 with the factor of1
or -1 would be relatively prime integers.

Regards,
Dmitry Popov

Argonne, IL
USA

[Popov, Dmitry Yu]

Thank you very much. List comprehensions make code much more concise indeed. Do list comprehensions also improve the speed of calculations?
________________________________
From: ***@gmail.com <***@gmail.com>
Sent: Friday, July 12, 2024 6:57 PM
To: Popov, Dmitry Yu <***@anl.gov>; 'Popov, Dmitry Yu via Python-list' <python-***@python.org>; ***@gmail.com <***@gmail.com>
Subject: RE: Relatively prime integers in NumPy

Dmitry, I clearly did not understand what you wanted earlier as you had not made clear that in your example, you already had progressed to some level where you had the data and were now doing a second step. So, I hesitate to say much until
ZjQcmQRYFpfptBannerStart
This Message Is From an External Sender
This message came from outside your organization.

ZjQcmQRYFpfptBannerEnd

Dmitry,



I clearly did not understand what you wanted earlier as you had not made clear that in your example, you already had progressed to some level where you had the data and were now doing a second step. So, I hesitate to say much until either nobody else addressed the issue (as clearly some have) or you explain well enough.



I am guessing you have programming experience in other languages and are not as “pythonic” as some. The code you show may not be quite how others might do it. Some may write mch of your code as a single line of python using a list comprehension such as:



hkl_list = [ [h, k, l] for SOMETHING in RANGE for SOMETHING2 in RANGE2 for SOMETHING3 in RANGE3]



Where h, k. l come from the somethings.



Back to the real world.





From: Popov, Dmitry Yu <***@anl.gov>
Sent: Friday, July 12, 2024 1:13 PM
To: ***@gmail.com; 'Popov, Dmitry Yu via Python-list' <python-***@python.org>; ***@gmail.com; Popov, Dmitry Yu <***@anl.gov>
Subject: Re: Relatively prime integers in NumPy



Thank you very much, Oscar.



Using the following code looks like a much better solution than my current Python code indeed.

np.gcd.reduce(np.transpose(a))

or

np.gcd.reduce(a,1)



The next question is how I can generate ndarray of h,k,l indices. This can be easily done from a Python list by using the following code.



import numpy as np

hkl_list=[]

for h in range(0, max_h):

      for k in range(0, max_k):

            for l in range(0, max_l):

                  hkl_local=[]

                  hkl_local.append(h)

                  hkl_local.append(k)

                  hkl_local.append(l)

                  hkl_list.append(hkl_local)

hkl=np.array(hkl_list, dtype=np.int64)

This code will generate a two-dimensional ndarray of h,k,l indices but is it possible to make a faster routine with NumPy?



Regards,

Dmitry







________________________________

From: Python-list <python-list-bounces+dpopov=***@python.org<mailto:python-list-bounces+dpopov=***@python.org>> on behalf of Popov, Dmitry Yu via Python-list <python-***@python.org<mailto:python-***@python.org>>
Sent: Thursday, July 11, 2024 2:25 PM
To: ***@gmail.com<mailto:***@gmail.com> <***@gmail.com<mailto:***@gmail.com>>; 'Popov, Dmitry Yu via Python-list' <python-***@python.org<mailto:python-***@python.org>>
Subject: Re: Relatively prime integers in NumPy



Thank you for your interest. My explanation is too concise indeed, sorry. So far, I have used Python code with three enclosed 'for' loops for this purpose which is pretty time consuming. I'm trying to develop a NumPy based code to make this

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender

This message came from outside your organization.



ZjQcmQRYFpfptBannerEnd

Thank you for your interest. My explanation is too concise indeed, sorry. So far, I have used Python code with three enclosed 'for' loops for this purpose which is pretty time consuming. I'm trying to develop a NumPy based code to make this procedure faster. This routine is kind of 'heart' of the algorithm to index of X-ray Laue diffraction patterns. In our group we have to process huge amount of such patterns. They are collected at a synchrotron radiation facility. Faster indexation routine would help a lot.



This is the code I'm currently using. Any prompts how to implement it in NumPy would be highly appreciated.



for h in range(0, max_h):

      for k in range(0, max_k):

            for l in range(0, max_l):

                  chvec=1

                  maxmult=2

                  if h > 1:                     

                        maxmult=h

                  if k > 1:

                        maxmult=k

                  if l > 1:

                        maxmult=l

                  if h > 1:

                        if maxmult > h:

                              maxmult=h

                  if k > 1:

                        if maxmult > k:

                              maxmult=k

                  if l > 1:

                        if maxmult > l:

                              maxmult=l

                  maxmult=maxmult+1

                  for innen in range(2, maxmult):

                        if h in range(0, (max_h+1), innen):

                              if k in range(0, (max_k+1), innen):

                                    if l in range(0, (max_l+1), innen):

                                          chvec=0

                  if chvec==1:

                        # Only relatively prime integers h,k,l pass to this block of the code





________________________________

From: ***@gmail.com<mailto:***@gmail.com> <***@gmail.com<mailto:***@gmail.com>>

Sent: Thursday, July 11, 2024 1:22 PM

To: Popov, Dmitry Yu <***@anl.gov<mailto:***@anl.gov>>; 'Popov, Dmitry Yu via Python-list' <python-***@python.org<mailto:python-***@python.org>>

Subject: RE: Relatively prime integers in NumPy



Дмитрий, You may think you explained what you wanted but I do not see what result you expect from your examples. Your request is a bit too esoteric to be a great candidate for being built into a module like numpy for general purpose se but

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender

This message came from outside your organization.



ZjQcmQRYFpfptBannerEnd



Дмитрий,



You may think you explained what you wanted but I do not see what result you

expect from your examples.



Your request is a bit too esoteric to be a great candidate for being built

into a module like numpy for general purpose se but I can imagine it could

be available in modules build on top of numpy.



Is there a reason you cannot solve this mostly outside numpy?



It looks like you could use numpy to select the numbers you want to compare,

then call one of many methods you can easily search for to see how to use

python to make some list or other data structure for divisors of each number

involved and then use standard methods to compare the lists and exact common

divisors. If needed, you could then put the results back into your original

data structure using numpy albeit the number of matches can vary.



Maybe a better explanation is needed as I cannot see what your latter words

about -1 and 1 are about. Perhaps someone else knows.









-----Original Message-----

From: Python-list <python-list-bounces+avi.e.gross=***@python.org<mailto:python-list-bounces+avi.e.gross=***@python.org>> On

Behalf Of Popov, Dmitry Yu via Python-list

Sent: Monday, July 8, 2024 3:10 PM

To: Popov, Dmitry Yu via Python-list <python-***@python.org<mailto:python-***@python.org>>

Subject: Relatively prime integers in NumPy



Dear Sirs.



Does NumPy provide a simple mechanism to identify relatively prime integers,

i.e. integers which don't have a common factor other than +1 or -1? For

example, in case of this array:

[[1,5,8],

[2,4,8],

[3,3,9]]

I can imagine a function which would return array of common factors along

axis 0: [1,2,3]. Those triples of numbers along axis 1 with the factor of1

or -1 would be relatively prime integers.



Regards,

Dmitry Popov



Argonne, IL

USA
--
https://urldefense.us/v3/__https://mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!ZGK1ZXYgmC6cpNa1xTXVTNklhunjYiinwaDe_xE3sJyVs4ZcVgUB_v2FKvDzDspx7IzFCZI7JpFsiV5iH58P$<https://urldefense.us/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!ZGK1ZXYgmC6cpNa1xTXVTNklhunjYiinwaDe_xE3sJyVs4ZcVgUB_v2FKvDzDspx7IzFCZI7JpFsiV5iH58P$-->

<https://urldefense.us/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!ZGK1ZXYgmC6cpNa1xTXVTNklhunjYiinwaDe_xE3sJyVs4ZcVgUB_v2FKvDzDspx7IzFCZI7JpFsiV5iH58P$-->

<https://urldefense.us/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!ZGK1ZXYgmC6cpNa1xTXVTNklhunjYiinwaDe_xE3sJyVs4ZcVgUB_v2FKvDzDspx7IzFCZI7JpFsiV5iH58P$-->

--<https://urldefense.us/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!ZGK1ZXYgmC6cpNa1xTXVTNklhunjYiinwaDe_xE3sJyVs4ZcVgUB_v2FKvDzDspx7IzFCZI7JpFsiV5iH58P$-->

https://urldefense.us/v3/__https://mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!avZA_RNHnI2aBy2E2Z3kwPCY3B4aDtoxObit540PzHeIW_4s1Tkkq5NapXL3KzGXv2BTWbYQJHf6AskeTC-IEA$<https://urldefense.us/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!avZA_RNHnI2aBy2E2Z3kwPCY3B4aDtoxObit540PzHeIW_4s1Tk

[a***@gmail.com]

Dmitry,



Efficiency of several kinds is hotly debated and sometimes it depends a lot on what is done within loops.



Many suggest a mild speed up of some comprehensions over loops but the loops are not gone but somewhat hidden and perhaps some aspects are faster for having been written in C carefully and not interpreted.



Comprehensions (and there are other versions that generate dictionaries and tuples and sets) may also be sped up a bit for other reasons like your fairly expensive APPPEND that has to keep finding the end o f a growing list and is not done the same way in a comprehension.



If you do a search, you find many opinions including on using functional programming techniques such as map/reduce. There are also



Your particular case is interesting because it just makes all combination of three variables. Some languages, like R, have functions that do this for you, like expand.grd. Python has many modules, like itertools that do things including combinations but perhaps not designed for your case.



Here is a version of your scenario:



import itertools

a = range(3)

b = range(4)

c = range(5)



list(itertools.product(a,b,c))

list(itertools.product(a,b,c))

[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4), (0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 0), (0, 2, 1), (0, 2, 2), (0, 2, 3), (0, 2, 4), (0, 3, 0), (0, 3, 1), (0, 3, 2), (0, 3, 3), (0, 3, 4), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 0, 3), (1, 0, 4), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 0), (1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 0), (1, 3, 1), (1, 3, 2), (1, 3, 3), (1, 3, 4), (2, 0, 0), (2, 0, 1), (2, 0, 2), (2, 0, 3), (2, 0, 4), (2, 1, 0), (2, 1, 1), (2, 1, 2), (2, 1, 3), (2, 1, 4), (2, 2, 0), (2, 2, 1), (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 0), (2, 3, 1), (2, 3, 2), (2, 3, 3), (2, 3, 4)]

import pprint
pprint.pprint(list(itertools.product(a,b,c)))

[(0, 0, 0),

(0, 0, 1),

(0, 0, 2),

(0, 0, 3),

(0, 0, 4),

(0, 1, 0),

(0, 1, 1),

(0, 1, 2),

(0, 1, 3),

(0, 1, 4),

(0, 2, 0),

(0, 2, 1),

(0, 2, 2),

(0, 2, 3),

(0, 2, 4),

(0, 3, 0),

(0, 3, 1),

(0, 3, 2),

(0, 3, 3),

(0, 3, 4),

(1, 0, 0),

(1, 0, 1),

(1, 0, 2),

(1, 0, 3),

(1, 0, 4),

(1, 1, 0),

(1, 1, 1),

(1, 1, 2),

(1, 1, 3),

(1, 1, 4),

(1, 2, 0),

(1, 2, 1),

(1, 2, 2),

(1, 2, 3),

(1, 2, 4),

(1, 3, 0),

(1, 3, 1),

(1, 3, 2),

(1, 3, 3),

(1, 3, 4),

(2, 0, 0),

(2, 0, 1),

(2, 0, 2),

(2, 0, 3),

(2, 0, 4),

(2, 1, 0),

(2, 1, 1),

(2, 1, 2),

(2, 1, 3),

(2, 1, 4),

(2, 2, 0),

(2, 2, 1),

(2, 2, 2),

(2, 2, 3),

(2, 2, 4),

(2, 3, 0),

(2, 3, 1),

(2, 3, 2),

(2, 3, 3),

(2, 3, 4)]



I think that is close enough to what you want but is it faster? You can try a benchmarking method on alternatives.









From: Popov, Dmitry Yu <***@anl.gov>
Sent: Friday, July 12, 2024 11:10 PM
To: ***@gmail.com; 'Popov, Dmitry Yu via Python-list' <python-***@python.org>; ***@gmail.com
Subject: Re: Relatively prime integers in NumPy



Thank you very much. List comprehensions make code much more concise indeed. Do list comprehensions also improve the speed of calculations?

_____

From: ***@gmail.com <mailto:***@gmail.com> <***@gmail.com <mailto:***@gmail.com> >
Sent: Friday, July 12, 2024 6:57 PM
To: Popov, Dmitry Yu <***@anl.gov <mailto:***@anl.gov> >; 'Popov, Dmitry Yu via Python-list' <python-***@python.org <mailto:python-***@python.org> >; ***@gmail.com <mailto:***@gmail.com> <***@gmail.com <mailto:***@gmail.com> >
Subject: RE: Relatively prime integers in NumPy



Dmitry, I clearly did not understand what you wanted earlier as you had not made clear that in your example, you already had progressed to some level where you had the data and were now doing a second step. So, I hesitate to say much until

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender

This message came from outside your organization.



ZjQcmQRYFpfptBannerEnd

Dmitry,



I clearly did not understand what you wanted earlier as you had not made clear that in your example, you already had progressed to some level where you had the data and were now doing a second step. So, I hesitate to say much until either nobody else addressed the issue (as clearly some have) or you explain well enough.

Ditr

I am guessing you have programming experience in other languages and are not as “pythonic” as some. The code you show may not be quite how others might do it. Some may write mch of your code as a single line of python using a list comprehension such as:



hkl_list = [ [h, k, l] for SOMETHING in RANGE for SOMETHING2 in RANGE2 for SOMETHING3 in RANGE3]



Where h, k. l come from the somethings.



Back to the real world.





From: Popov, Dmitry Yu <***@anl.gov <mailto:***@anl.gov> >
Sent: Friday, July 12, 2024 1:13 PM
To: ***@gmail.com <mailto:***@gmail.com> ; 'Popov, Dmitry Yu via Python-list' <python-***@python.org <mailto:python-***@python.org> >; ***@gmail.com <mailto:***@gmail.com> ; Popov, Dmitry Yu <***@anl.gov <mailto:***@anl.gov> >
Subject: Re: Relatively prime integers in NumPy



Thank you very much, Oscar.



Using the following code looks like a much better solution than my current Python code indeed.

np.gcd.reduce(np.transpose(a))
or
np.gcd.reduce(a,1)

The next question is how I can generate ndarray of h,k,l indices. This can be easily done from a Python list by using the following code.

import numpy as np
hkl_list=[]
for h in range(0, max_h):
      for k in range(0, max_k):
            for l in range(0, max_l):
                  hkl_local=[]
                  hkl_local.append(h)
                  hkl_local.append(k)
                  hkl_local.append(l)
                  hkl_list.append(hkl_local)
hkl=np.array(hkl_list, dtype=np.int64)
This code will generate a two-dimensional ndarray of h,k,l indices but is it possible to make a faster routine with NumPy?

Regards,
Dmitry



_____


From: Python-list <python-list-bounces+dpopov=***@python.org <mailto:python-list-bounces+dpopov=***@python.org> > on behalf of Popov, Dmitry Yu via Python-list <python-***@python.org <mailto:python-***@python.org> >
Sent: Thursday, July 11, 2024 2:25 PM
To: ***@gmail.com <mailto:***@gmail.com> <***@gmail.com <mailto:***@gmail.com> >; 'Popov, Dmitry Yu via Python-list' <python-***@python.org <mailto:python-***@python.org> >
Subject: Re: Relatively prime integers in NumPy



Thank you for your interest. My explanation is too concise indeed, sorry. So far, I have used Python code with three enclosed 'for' loops for this purpose which is pretty time consuming. I'm trying to develop a NumPy based code to make this

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender

This message came from outside your organization.



ZjQcmQRYFpfptBannerEnd

Thank you for your interest. My explanation is too concise indeed, sorry. So far, I have used Python code with three enclosed 'for' loops for this purpose which is pretty time consuming. I'm trying to develop a NumPy based code to make this procedure faster. This routine is kind of 'heart' of the algorithm to index of X-ray Laue diffraction patterns. In our group we have to process huge amount of such patterns. They are collected at a synchrotron radiation facility. Faster indexation routine would help a lot.

This is the code I'm currently using. Any prompts how to implement it in NumPy would be highly appreciated.

for h in range(0, max_h):
      for k in range(0, max_k):
            for l in range(0, max_l):
                  chvec=1
                  maxmult=2
                  if h > 1:                     
                        maxmult=h
                  if k > 1:
                        maxmult=k
                  if l > 1:
                        maxmult=l
                  if h > 1:
                        if maxmult > h:
                              maxmult=h
                  if k > 1:
                        if maxmult > k:
                              maxmult=k
                  if l > 1:
                        if maxmult > l:
                              maxmult=l
                  maxmult=maxmult+1
                  for innen in range(2, maxmult):
                        if h in range(0, (max_h+1), innen):
                              if k in range(0, (max_k+1), innen):
                                    if l in range(0, (max_l+1), innen):
                                          chvec=0
                  if chvec==1:
                        # Only relatively prime integers h,k,l pass to this block of the code


________________________________
From: ***@gmail.com <mailto:***@gmail.com> <***@gmail.com <mailto:***@gmail.com> >
Sent: Thursday, July 11, 2024 1:22 PM
To: Popov, Dmitry Yu <***@anl.gov <mailto:***@anl.gov> >; 'Popov, Dmitry Yu via Python-list' <python-***@python.org <mailto:python-***@python.org> >
Subject: RE: Relatively prime integers in NumPy

Дмитрий, You may think you explained what you wanted but I do not see what result you expect from your examples. Your request is a bit too esoteric to be a great candidate for being built into a module like numpy for general purpose se but
ZjQcmQRYFpfptBannerStart
This Message Is From an External Sender
This message came from outside your organization.

ZjQcmQRYFpfptBannerEnd

Дмитрий,

You may think you explained what you wanted but I do not see what result you
expect from your examples.

Your request is a bit too esoteric to be a great candidate for being built
into a module like numpy for general purpose se but I can imagine it could
be available in modules build on top of numpy.

Is there a reason you cannot solve this mostly outside numpy?

It looks like you could use numpy to select the numbers you want to compare,
then call one of many methods you can easily search for to see how to use
python to make some list or other data structure for divisors of each number
involved and then use standard methods to compare the lists and exact common
divisors. If needed, you could then put the results back into your original
data structure using numpy albeit the number of matches can vary.

Maybe a better explanation is needed as I cannot see what your latter words
about -1 and 1 are about. Perhaps someone else knows.




-----Original Message-----
From: Python-list <python-list-bounces+avi.e.gross=***@python.org <mailto:python-list-bounces+avi.e.gross=***@python.org> > On
Behalf Of Popov, Dmitry Yu via Python-list
Sent: Monday, July 8, 2024 3:10 PM
To: Popov, Dmitry Yu via Python-list <python-***@python.org <mailto:python-***@python.org> >
Subject: Relatively prime integers in NumPy

Dear Sirs.

Does NumPy provide a simple mechanism to identify relatively prime integers,
i.e. integers which don't have a common factor other than +1 or -1? For
example, in case of this array:
[[1,5,8],
[2,4,8],
[3,3,9]]
I can imagine a function which would return array of common factors along
axis 0: [1,2,3]. Those triples of numbers along axis 1 with the factor of1
or -1 would be relatively prime integers.

Regards,
Dmitry Popov

Argonne, IL
USA

--
https://urldefense.us/v3/__https://mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!ZGK1ZXYgmC6cpNa1xTXVTNklhunjYiinwaDe_xE3sJyVs4ZcVgUB_v2FKvDzDspx7IzFCZI7JpFsiV5iH58P$ <https://urldefense.us/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!ZGK1ZXYgmC6cpNa1xTXVTNklhunjYiinwaDe_xE3sJyVs4ZcVgUB_v2FKvDzDspx7IzFCZI7JpFsiV5iH58P$-->
<https://urldefense.us/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!ZGK1ZXYgmC6cpNa1xTXVTNklhunjYiinwaDe_xE3sJyVs4ZcVgUB_v2FKvDzDspx7IzFCZI7JpFsiV5iH58P$-->
<https://urldefense.us/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!ZGK1ZXYgmC6cpNa1xTXVTNklhunjYiinwaDe_xE3sJyVs4ZcVgUB_v2FKvDzDspx7IzFCZI7JpFsiV5iH58P$-->
-- <https://urldefense.us/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!ZGK1ZXYgmC6cpNa1xTXVTNklhunjYiinwaDe_xE3sJyVs4ZcVgUB_v2FKvDzDspx7IzFCZI7JpFsiV5iH58P$-->
https://urldefense.us/v3/__https://mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!avZA_RNHnI2aBy2E2Z3kwPCY3B4aDtoxObit540PzHeIW_4s1Tkkq5NapXL3KzGXv2BTWbYQJHf6AskeTC-IEA$ <https://urldefense.us/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!G_uCfscf7eWS!avZA_RNHnI2aBy2E2Z3kwPCY3B4aDtoxObit540PzHeIW_4s1Tkkq5NapXL3KzGXv2BTWbYQJHf6AskeTC-IEA$>