的功能中输入小的变化总是导致大的变化，输出 [英] A function where small changes in input always result in large changes in output

问题描述

我想一个算法函数接受n个整数，并返回有一个整数。对于输入的微小变化，由此产生的整数应该相差很大。尽管我已经采取了一系列的数学课程，我没有使用过的知识非常多，现在我需要一些帮助......

I would like an algorithm for a function that takes n integers and returns one integer. For small changes in the input, the resulting integer should vary greatly. Even though I've taken a number of courses in math, I have not used that knowledge very much and now I need some help...

此功能的一个重要特性应该是，如果是用与坐标对作为输入，其结果被绘制（作为例如一个灰度值）的图像上，任何重复图案只应可见如果图像是非常大了。

An important property of this function should be that if it is used with coordinate pairs as input and the result is plotted (as a grayscale value for example) on an image, any repeating patterns should only be visible if the image is very big.

我已经尝试用伪随机数不同的算法，但收效甚微，最后忽然想起了MD5几乎符合我的标准，但它是不是数字（至少不是从我所知道的）。这导致了这样的事情的Python原型（对于n = 2，它可以很容易地改变拿当然是一个整数列表）：

I have experimented with various algorithms for pseudo-random numbers with little success and finally it struck me that md5 almost meets my criteria, except that it is not for numbers (at least not from what I know). That resulted in something like this Python prototype (for n = 2, it could easily be changed to take a list of integers of course):

import hashlib
def uniqnum(x, y):
    return int(hashlib.md5(str(x) + ',' + str(y)).hexdigest()[-6:], 16)

但显然感到不对劲走了过来字符串时，输入和输出都是整数。什么将是一个很好的替代这个实现（伪code，Python或任何语言）？

But obviously it feels wrong to go over strings when both input and output are integers. What would be a good replacement for this implementation (in pseudo-code, python, or whatever language)?

推荐答案

一个哈希是为了解决该解决方案的完全您所描述的问题。请参见维基百科的文章

A "hash" is the solution created to solve exactly the problem you are describing. See wikipedia's article

您使用的将是很好的任何哈希函数;哈希函数往往根据这些标准来进行判断：

Any hash function you use will be nice; hash functions tend to be judged based on these criteria:

• 的程度他们prevent的碰撞的（两个独立的输入端产生相同的输出） - 这一个副产品是该函数最小化输出，可能永远不会程度从任何输入到达。
• 在其产出分配给一个均匀分布组输入的均匀性
• 在何种程度上输入的微小变化产生大的变化的输出。

• The degree to which they prevent collisions (two separate inputs producing the same output) -- a by-product of this is the degree to which the function minimizes outputs that may never be reached from any input.
• The uniformity the distribution of its outputs given a uniformly distributed set of inputs
• The degree to which small changes in the input create large changes in the output.

（见完善哈希函数）

由于它是如何努力创造一个散列函数最大化所有这些标准，为什么不直接使用的最常用的依赖，对现存的函数有1已经是？

Given how hard it is to create a hash function that maximizes all of these criteria, why not just use one of the most commonly used and relied-on existing hash functions there already are?

这是什么，似乎，把整数转换为字符串似乎像加密另一层！ （这是很好的为您的目的，我会承担）

From what it seems, turning integers into strings almost seems like another layer of encryption! (which is good for your purposes, I'd assume)

不过，你的问题问的是处理的散列函数专门与数字，所以在这里我们去。

However, your question asks for hash functions that deal specifically with numbers, so here we go.

如果你想借用已有的算法，你可能想涉足的 伪随机数发生器

If you want to borrow already-existing algorithms, you may want to dabble in pseudo-random number generators

一个简单的一种是中间方的方法：

One simple one is the middle square method:

• 以一个数字
• 广场它
• 砍掉数字并留下中间的数字与相同长度的原件。

即

1111 => 01234321 => 2342

那么，1111将是散列到2342，在广场中间的方法。

so, 1111 would be "hashed" to 2342, in the middle square method.

这个方法是不是是有效的，但对于哈希几号，这具有非常低的碰撞率，均匀分布，和巨大的乱势（小的变化=>大的变化） 。但如果你有多个值，时间去寻找别的东西......

This way isn't that effective, but for a few number of hashes, this has very low collision rates, a uniform distribution, and great chaos-potential (small changes => big changes). But if you have many values, time to look for something else...

在盛大的爸爸都切实有效，简单的随机数生成的是（梅森倍捻机）http://en.wikipedia.org/wiki/Mersenne_twister。事实上，一个实现可能是在那里每一个编程语言可想而知。你的散列输入的东西，将在他们的术语中被称为种子。

The grand-daddy of all feasibly efficient and simple random number generators is the (Mersenne Twister)[http://en.wikipedia.org/wiki/Mersenne_twister]. In fact, an implementation is probably out there for every programming language imaginable. Your hash "input" is something that will be called a "seed" in their terminology.

在结束

1. 在没有错，基于字符串的哈希函数
2. 如果你想坚持的整数和花哨，尝试用你的电话号码作为一个伪随机数发生器的种子。

这篇关于的功能中输入小的变化总是导致大的变化，输出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！