问题标签 [deterministic]

我知道我无法在 C++/C 上比较两个浮点数或双精度数的绝对相等性。如果出于某种原因，我编写了一个使用绝对相等的 if 条件，是否可以保证 if 条件在程序的不同运行中为相同的数据返回相同的结果？或者它纯粹是不确定的，结果可能会有所不同？

我是这么想的，因为上限是 2^n，并且鉴于它们都是有限机器，n 状态 NFA 和具有 2^n 或更少状态的 DFA 的交集将是有效的。

我在这里错了吗？

我有一个可以通过迭代解决的问题，但我想知道是否有使用正则表达式的更优雅的解决方案和split()

我有一个字符串（excel放在剪贴板上），本质上是逗号分隔的。需要注意的是，当单元格值包含逗号时，整个单元格会用引号括起来（大概是为了转义该字符串中的逗号）。示例字符串如下：

现在，我想优雅地将此字符串拆分为单个单元格，但问题是我不能使用以逗号作为分隔符的正常拆分表达式，因为它会拆分值中包含逗号的单元格。另一种看待这个问题的方法是，如果逗号前面有偶数个引号，我只能用逗号分割。

这很容易用循环解决，但我想知道是否有一个正则表达式.split 函数能够捕获这个逻辑。为了解决这个问题，我为逻辑构造了确定性有限自动机 (DFA)。

现在的问题被简化为以下问题：有没有办法拆分这个字符串，以便在 DFA 中每次达到最终状态（此处为状态 4）时产生一个新的数组元素（对应于 /s）？

我正在一个网站上运行 n 个拆分测试。我想将一个均匀分布的整数用户 ID 分配给 n 个存储桶之一，并且确定性地使同一用户始终获得相同的测试。

此时，我可以通过将用户 ID 修改为 n 来在拆分测试列表中选择一个索引。如果我想对某些测试进行加权怎么办？

例如，桶 #1/21 分配了 90% 的时间，其余 20 个测试分配了 0.5% 的时间。

我觉得我可以以某种方式扩大我的列表的大小，并且仍然使用 mod 技术来实现这一点，但是在内存中拥有潜在的巨大的临时列表似乎并不优雅。

有人可以给我一个程序中确定性错误的例子吗？

谢谢。

我正在使用 QueryPerformanceCounter 在我的应用程序中进行一些计时。但是，在运行几天后，该应用程序似乎停止正常运行。如果我只是重新启动应用程序，它就会再次开始工作。这让我相信我的计时代码中有溢出问题。

我的问题是上面的代码是否应该在连续运行数周内确定性地工作？

如果不是，问题出在哪里？我以为溢出是由

但也许这还不够？

编辑：请注意，我没有编写原始代码，Ryan M. Geiss 做了，代码原始源的链接在代码中。

DETERMINISTIC现在，当我使用运算符右侧的函数时，我遇到了一个非常棘手的问题，即 Oracle 执行计划运行严重LIKE。这是我的情况：

情况

我认为执行这样的查询是明智的（简化）：

我会绑定?到类似'Eder%'. 现在customers和addresses是非常大的桌子。这就是为什么使用索引很重要的原因。当然，在addresses.cust_id. 但我还在 上创建了一个基于函数的索引special_char_filter(customers.surname)，效果非常好。

麻烦

问题是，上述涉及like子句的查询创建了带有 FULL TABLE SCANS on 的执行计划addresses。看起来此查询中的某些内容使 Oracle 无法在addresses.cust_id.

解决方法

我发现，我的问题的解决方案是这样的：

我DETERMINISTIC从 like 运算符的右侧删除了 (!) 函数，并在 Java 中预先计算了绑定变量。现在这个查询是超快的，没有任何 FULL TABLE SCANS。这也非常快（虽然不等价）：

混乱

我不明白这一点。在运算符右侧设置确定性函数有什么问题like？我在 Oracle 11.2.0.1.0 中观察到了这一点

这是我在这个网站上的第一个问题，我对RSA只有基本的数学了解，所以请多多包涵！:)

我正在为我在大学的最后一年项目编写一个 Java Web 应用程序。这是一个基于网络的“Pret-a-voter”实现，一个安全的投票系统，对于那些听说过它的人来说。

本质上，我的问题是我希望能够让某人担任审计员的角色：

• 源字节数组（要加密的明文）
• 一个 RSA 公钥文件
• 一个“目标”字节数组，这是我自己计算给定明文和公钥的密码数据的结果

然后，我希望审核员能够使用前两项执行加密，并对第三项是结果感到满意。因此，我需要确定性的加密，即每次重复使用相同的明文和公钥进行加密时生成相同的密码数据。

（注意 - 我在这个项目中使用非常小的数据块 - 根本不涉及对称加密......我知道这是 RSA 的“有趣”使用！）

无论如何我发现在Java中，使用

使用默认的随机填充方案，成本为 11 个字节（因此使用 2048 位密钥对，可以加密 2048/8-11 = 245 个字节）。相同明文的重复加密会产生不同的密文，这显然不是我想要的ECB模式。

我的问题是 -我应该使用以下内容吗？

我在很多地方读到 RSA 在没有填充的情况下是不安全的。这仅仅是因为攻击者可以构建明文/密文字典吗？这是我需要的确定性加密的副作用，以允许审核员验证我的加密，并且在我的方案中，审核员是受信任的，所以可以。

我的问题的第二部分与 java 相关。如果我确实如上所述使用 RSA/ECB/NoPadding，我相信我能够提供（比如说）长度为 128 的源字节数组（对于 1024 位 RSA 密钥对）并对其进行加密以获得另一个长度的字节数组128. 如果我然后尝试使用不同的 1024 长度的公钥再次加密它，我得到

javax.crypto.BadPaddingException：消息大于模数

有谁知道为什么？

编辑 - 使用 NoPadding 加密并不总是产生这个异常 - 它是喜怒无常的。然而，即使加密没有产生这个异常，解密也会产生这个：

javax.crypto.BadPaddingException：数据必须从零开始

非常感谢您阅读本文！任何帮助将不胜感激。

编辑 - 抱歉，我最初的问题不是很清楚我想要做什么，所以这里有一个 [attempt at an] 解释：

• 明文是选民在选举中的投票。
• Pret-a-voter 旨在在不牺牲选民机密性（等）的情况下进行端到端的验证。投票后，选民将获得一张收据，他们可以使用该收据来验证他们的投票是否被正确记录，并且稍后会向他们表明他们的投票没有被篡改。选民将其收据上的信息与发布在网络上的相同副本进行比较。
• 但是，任何选民都不可能证明他/她是如何投票的（因为这可能会导致强制），因此信息不是明文，而是投票的加密副本。
• 事实上，明文被加密了四次，使用四个不同的非对称密钥——由两个不同的柜员持有，每个柜员持有两个密钥。因此，向一个出纳员提供投票（明文），该出纳员使用公钥＃1对其进行加密，然后用他的第二个公钥加密该密文，将该密文提供给第二个出纳员，该出纳员使用他的两个密钥对其进行加密方式。生成的密文（四次连续加密的结果）是发布到网络（公开）的内容。出纳员是值得信赖的。
• 每个加密投票都可以可视化为一个“洋葱”，其中中心是投票，并且有几层加密。为了进行投票，必须依次删除每一层，这意味着必须以相反的顺序应用相应的私钥（由出纳员持有）。这是安全的关键——所有出纳员必须合作才能解密选票。
• 网络公告板可以可视化为一个有 5 列的表格 - 第一列（左侧）保存完全加密的选票（也显示在每个选民的收据上），并且是投票阶段唯一可见的列。第二列包含相同的选票集，但移除了外层 - 出纳员 2 通过在计票阶段使用其私钥解密选票来填充此列和第 3 列。在计票阶段结束时，第 5 列包含可以计票的完全解密的选票。
• 每个选民都会收到一张收据，将他们链接到第 1 列中的加密投票。这不会显示他们的投票方式，但允许他们验证他们的投票没有被篡改，因为在整个选举过程中，他们可以验证他们的加密投票仍然存在于第 1 列中，未触及。当然，这只是“端到端验证”的一半，因为选民无法验证解密是否正确完成，即第 2 列中有一个条目，即他们的投票减去外层加密. 每个选民只负责验证直到第 1 列的点。
• 此后，审核员有责任检查第 1 列中的条目是否解密到第 2 列，依此类推。他们这样做的方式是依靠确定性加密和公开的用于加密的公钥。
• 由于公钥是公开的，您不希望人们简单地从第 5 列到第 1 列画线，在重复加密时加入某人的投票 - 这样，将您与加密投票联系起来的收据实际上将您与未加密、可读的投票 --> 强制！因此，只有第 1、3 和 5 列是公开的（这就是每个出纳员执行两次加密的原因），并且对于第 3 列中的每个条目，只有 {2,4} 中的一个对应条目向审计员显示。这可以防止任何人（甚至审计员）将加密投票与未加密投票联系起来。
• 因此，审计员需要在第 3 列中输入一个条目，在第 2 列中给出相应的条目和公钥，并执行相同的加密以验证他们确实获得了第 2 列中的条目。
• 总之，这提供了端到端的可验证性。

抱歉，太长了——我希望它描述了我对确定性加密的需求。我错过了很多基本细节（我已经对这个方案进行了大量修改），但希望核心原则都在那里。非常感谢您阅读 - 我真的很感激。

我有一个计算 n 体问题的 Java 程序。在每次迭代中，它都会检查每个物体对其他物体施加的力，然后根据这些力移动它们。

身体总是从同一个地方开始（我把它们排列成一个圆圈，从身体 0 到身体 n），它们总是被检查并以相同的顺序移动（从身体 0 到 n）。但是，当我运行该程序 30 次时，我得到的运行时间截然不同。一个运行时间为 2,947,188 毫秒（49 分钟），而另一个运行时间为 920,967 毫秒（15 分钟）。我对这些时间的数量级并不感到惊讶，因为我在很多物体上使用了蛮力方法 (O(n^2))。但我想知道为什么确定性算法会有这样的差异？如果一次又一次使用相同的算法，那么运行时间不应该相同（或至少接近）吗？

在你问之前，是的，我正在测量进行计算的线程的时间，而不是挂钟时间。

编辑-我正在这样测量时间：

除了计算步骤之外，这是否测量任何其他内容？

第二次编辑-现在我将其更改为像这样测量时间：

然而，结果仍然不可重复。我还尝试使用标志 -Xint 运行我的程序，结果仍然不可重复。

假设问题出在算法和多线程中是否安全？或者它仍然是与Java有关的问题吗？

我目前正在开发一个用 C++ 和 C# 编写的（遗留）程序；它执行一些重量级计算，但应该是完全确定的。即相同的输入将产生相同的输出......问题是2次运行（在同一台计算机上，使用相同的编译可执行文件）产生略有不同的输出。

应用程序读取和写入 SQL Server 数据库（它对 DB 具有唯一的访问权限，因此不应有其他任何东西干扰 DB 值）。

运行之间唯一明显的区别是它们每个都被分配了一个唯一的名称（只是一个字符串变量）。

代码中没有随机对象，所有循环都运行预定次数的迭代或直到满足条件，它们不会运行一定的时间。有少量的多线程，我确信它是线程安全的，但我会自己检查一下。

我应该寻找其他明显的东西，这会导致这种异常行为吗？