Numpy 中某个矩阵的平方距离计算方法

目录

具体流程

1.假设：有一个n*m的矩阵，其内部为n个m维点的坐标：

rand = np.random.RandomState(42)

x = rand.randint(0, 10, (3, 2))

x
Out[332]: 
array([[6, 3],
       [7, 4],
       [6, 9]])

2.计算在坐标系中每对点的差值

difference = x[:, None, :] - x[None, :, :]

difference.shape
Out[334]: (3, 3, 2)

difference
Out[335]: 
array([[[ 0,  0],
        [-1, -1],
        [ 0, -6]],

       [[ 1,  1],
        [ 0,  0],
        [ 1, -5]],

       [[ 0,  6],
        [-1,  5],
        [ 0,  0]]])

3.计算出差值的平方

sq_ = difference ** 2

sq_.shape
Out[337]: (3, 3, 2)

sq_
Out[338]: 
array([[[ 0,  0],
        [ 1,  1],
        [ 0, 36]],

       [[ 1,  1],
        [ 0,  0],
        [ 1, 25]],

       [[ 0, 36],
        [ 1, 25],
        [ 0,  0]]], dtype=int32)

4.将差值求和得平方距离

dist = sq_.sum(-1)

dist
Out[341]: 
array([[ 0,  2, 36],
       [ 2,  0, 26],
       [36, 26,  0]], dtype=int32)

分析

从二维到三维的变化过程：

添加一个**np.newaxis**(等同于**None**)
**其实就是在对应的shape位置上加上一个*1***

如以下代码所示

x1 = x[:, None, :]

x2 = x[None, :, :]

x1.shape
Out[344]: (3, 1, 2)

x2.shape
Out[345]: (1, 3, 2)

那么对于这两个shape (3, 1, 2) 和 （1， 3， 2）而言
由numpy的广播原则最后两个shape 都会变成（3， 3， 2）

可以这样理解： 
认为现在是一个三维的坐标图
对于（3， 1， 2）而言，所有的值都在 xoz 平面上分布
对于（1， 3， 2）而言，所有的值都在 yoz 平面上分布

那么广播后：
xoz 平面上的点会沿着y轴向前复制三个相同的平面
yoz 平面上的点也会沿着x轴向前复制三个

那么必然在第一象限内两平面产生的这样两个3*3*2的空间会有交点
前述代码中第一步的减法即是在这些交点处执行了

平方无需多言

接下来是求和：

之前扩大维数的时候将点分别置于了两个侧平面
其中x， y轴均是表示点的个数
而z轴表示的是实际每个点的x，y坐标信息

那么不难理解： 
将z轴累加降维就可以得到两个点横纵坐标的平方和

最终得到的结果矩阵：
axis 0 和 axis 1 表示的都是每个点
交点处即为两点距离的平方

参考

《Python数据科学手册》

你好，我是罡罡同学！
代码谱第一页忘掉心上人，最后一页。。。。。。

前言

正在学习信息安全数学基础这门课程。
编程实现模重复平方计算法。

先介绍一下模重复平方算法

一、模重复平方算法

图片来自大学MOOC陈恭亮老师的视频中，稍有模糊。。。

下面我们用C语言来实现这个算法。我们可以思考一下，这个算法一共可以分为几个小部分？
首先，我们需要一个十进制转化为二进制的函数，主要用于将指数转化为二进制形式；
我们还需要知道，我们的循环计算需要执行多少次，所以我们需要一个函数来确定指数的位数；
最后一个函数就是我们的模重复平方计算函数了。当然我们还可以来定义一个打印函数。

废话不多说，上代码！！！

上代码！

#include<stdio.h>
#include<math.h>
int O_Binary(int n,int a[])//十进制转化为二进制函数 
{ int i,j,m; 
 for(m=0;m<15;m++)
 { i=n%2;
  j=n/2;
  n=j;
  a[m]=i;
 }
 for(m=15;m>=0;m--)//将数组倒序输出 
 { printf("%d",a[m]);
  if(m%4==0)//每隔四个数字打印一个空格 
   printf(" ");
 }
 printf("\n");
 return 0;
}
int judge_O_bit(int n)//表达十进制所需的位数 
{ int i=1;
 while(i)
 { if(n<pow(2,i))
  { 
   //printf("%d ",i);
   return i;
  }
  i++;
 }
}
int print(int a[])
{ int i;
 printf("将二进制存到数组中：\n\t");
 for(i=0;i<=15;i++)
 { printf("%d",a[i]);
  if((i+1)%4==0)//每隔四个数字打印一个空格 
   printf(" ");
 }
 return 0;
} 
int jisuan_Mod(int zhi,int di,int mo,int bit,int a[])//zhi 指数，di底数，mo模几，bit指数的二进制的位数  
{ int x,y,j;          //a[]存储指数的二进制，a[0]= 1 。。。。 
 printf("开始输出结果！-->>\n");
 y=di;
 for(j=0;j<bit;j++)
 { if(j==0)//第一次时 
  { x=di%mo;
   y=(y*y)%mo;
   printf("%d. n%d = %d\n",j+1,j,a[j]);
   printf("\ta%d ≡%d, b%d ≡%d(mod %d)\n",j,x,j+1,y,mo);
   continue;
  }
  if(a[j]==0&&j!=bit-1&&j!=0)//二进制为0 且不是最后一次 
  { x=x;//x不变，依旧为上一个x
   y=(y*y)%mo;
   printf("%d. n%d = %d\n",j+1,j,a[j]);
   printf("\ta%d ≡%d, b%d ≡%d(mod %d)\n",j,x,j+1,y,mo);
   continue;
  }
  else//二进制为1
  { x=(x*y)%mo; 
   if(j!=bit-1)
   { y=(y*y)%mo;//最后一次时不再算y，直接输出x即可
    printf("%d. n%d = %d\n",j+1,j,a[j]);
    printf("\ta%d ≡%d, b%d ≡%d(mod %d)\n",j,x,j+1,y,mo);continue;
   }
   printf("%d. n%d = %d\n",j+1,j,a[j]);
   printf("\ta%d ≡%d(mod %d)\n",j,x,mo);
   continue;
  }
 }
 printf("最后，计算出 %d^%d ≡%d(mod %d)",di,zhi,x,mo);
 return x;
}
int main()
{ int zhi,di,bit,i,yu,mo;
 int a[16]={0};
 printf("\t模重复平方计算\n");
 printf("请输入指数——十进制数字（0~32767）:");
 scanf("%d",&zhi);
 printf("请输入底数:");
 scanf("%d",&di);
 printf("请输入模数:");
 scanf("%d",&mo);//13的二进制位 1101 
 printf("指数转化为二进制:\n\t");
 O_Binary(zhi,a); //数组a存放指数的二进制，a[0]= 1 
 bit=judge_O_bit(zhi);
 print(a);
 printf("\n\n\n"); 
 jisuan_Mod(zhi,di,mo,judge_O_bit(zhi),a); 
 return 0;
}

第一道习题，成功。
第二道习题，成功。
下面我们再用JAVA来实现第二种计算方法（这种是我们老师讲的，比较好理解）
首先还是将指数转化为二进制的形式，需要注意的是，第一次初始化，用底数乘1。当二进制的高位为1时，将底数平方再乘上底数，当元素为0时，只平方即可。
我们举个例子吧，如下图所示。

上JAVA代码！

import java.util.Scanner;
/*2020/10/31 
 *模重复平方算法(罡罡同学)
 */
public class Demo3{
 public static void main(String[] args){
  Scanner pi = new Scanner(System.in);
  System.out.print("\t模重复平方法(罡罡同学)\n请输入指数：");
  int zhi=pi.nextInt();
  System.out.print("请输入底数：");
  int di=pi.nextInt();
  System.out.print("请输入模数：");
  int mo=pi.nextInt();
  String bin1 = Integer.toBinaryString(zhi);//4位
  System.out.println("指数转化为二进制： "+bin1);
  System.out.printf("最后结果为： %d^%d ≡"+count_mod(bin1,di,mo)+"(mod%d)",di,zhi,mo);
 }
 public static int count_mod(String s,int di,int mo)
 { int result=0;
  for(int i=0;i<s.length();i++)//s.length 可以替代参数zhi
  { if(i==0)
   {
    result=(di*1)%mo;continue;
   }
   if(s.charAt(i)=='1')
   {
    result=(result*result)*di%mo;
   }
   else
   {
    result=(result*result)%mo;
   }
  }
  return result;
 }
}

程序执行结果截图：

个人认为第二种方法更简单，而且还可以直接调用很多JAVA已经定义好的函数！！！
大家记得点赞呀！谢谢！